Codeforces 480C Riding in a Lift dp - c++编程基础

TOP

Codeforces 480C Riding in a Lift dp

2015-07-20 17:25:49 来源: 作者: 【大中小】浏览:2次

Tags：Codeforces 480C Riding Lift

题目链接：点击打开链接

题意：

给定 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<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 1631 Bridging signals（LIS ..	下一篇：HDU 3861 The King’s Problem（..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: