Codeforces 480C Riding in a Lift dp-白红宇

Codeforces 480C Riding in a Lift dp

阅读量：5836 次

发布时间：2019-06-18

本文共 1217 字，大约阅读时间需要 4 分钟。

主题链接：

意甲冠军：

特定 n a b k

构造一个长度k该序列。

使得序列中对于随意两个相邻的数 | w[i-1] - w[i] | < | w[i] - b |

且第一个数 |a - w[1] | < | w[1] - b |

问：

有多少种不同的序列。

思路：dp

对于粗暴的dp复杂度是 n^3

我们能够用前缀和来优化掉一维的dp。。

反正是简单粗暴的题。详细看代码吧。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            using namespace std;typedef long long ll;const int N = 5005;const ll mod = 1000000007;int a, b, K, n;ll dp[N][N], sum[N];void put(int k){ printf("%d:", k); for(int i = 1; i <= n; i++)pt(dp[k][i]),putchar(' '); puts("");}ll solve(){ dp[0][a] = 1; for(int k = 1; k <= K; k++) { sum[0] = 0; for(int i = 1; i <= n; i++) { sum[i] = sum[i-1] + dp[k-1][i]; if(sum[i] >= mod) sum[i] -= mod; } for(int i = 1, j; i <= n; i++) { if(i==b)continue; j = (b+i)>>1; if(i < b) { if(b-j <= j-i) j--; dp[k][i] = sum[j] - dp[k-1][i]; } else { if(j-b <= i-j) j++; dp[k][i] = sum[n] - sum[j-1] - dp[k-1][i]; } if(dp[k][i] < 0){ dp[k][i] %= mod; dp[k][i] += mod; } } } ll ans = 0; for(int i = 1; i <= n; i++){ ans += dp[K][i]; if(ans >= mod) ans -= mod; } return ans;}int main() { while(cin>>n>>a>>b>>K){ memset(dp, 0, sizeof dp); cout<