马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
AtCoder
我们肯定会先坐地铁，因此思量每个地铁之间怎么设立公交点。
标题要求我们盘算有几种设置方法，因此思量 dp。我们先坐了地铁，那么之后就只会坐公交了，以是对于每个地铁站之间的地段可以单独讨论，末了用乘法原理盘算。
对于差别的段，我们除了长度差别，另有左右两头可以走的长度差别。
在起始状态下，我们从右边来可以或许走的间隔比从左边来的环境少一格。
思量我们怎样设置站台选择，假如我们直接从左往右放，轻易忽略从右边来的环境，倒霉于盘算。
由于两边的可走长度差别，对盘算影响较大，我们思量把可走长度放到状态中。
假如仅仅纪录左右两边的长度，那么会出现我放了一个位置但是不知道紧缩左边还是右边的环境，非常贫苦。
以是思量类似求最短路的算法，我们先把可以走的更远的，也就是斲丧更少的放了。
由于起始时右边可走长度更短，以是先放左边，再放右边，以此类推，如许我们只须要纪录左边大概右边长度以及当前左右是否相当即可得到两边的可走长度。
如许状态中只须要纪录现在两边的间隔，某一边的可走长度，左右可走长度是否相当。
直接 dp 再通过前缀和优化即可。
代码：
[code]#include#define int long longusing namespace std;const int mod=1e9+7;int n,k,x,dp[10005][2],s[2505],pre[10005];signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>k>>x; for(int i=1;i>s; if(x |
发表于