首页 > 代码库 > CF 479E Riding in a Lift 前缀和 DP
CF 479E Riding in a Lift 前缀和 DP
输入 n a b k 有n层楼 起点在a层 b层是不能到达的 假设当前在x层 每一次可以到达y层 满足 |x-y| < |x-b| 求进行k次的不同方案数
dp[i][j]为第i次到达j层的方案数 dp[i][j] = sum(dp[i-1][k]) 其中|k-j| < |k-b|
满足条件的k是连续的一段 用前缀和优化
#include <cstdio> #include <cstring> #include <cstdlib> using namespace std; typedef long long LL; const int maxn = 5010; const int mod = 1000000007; LL dp[maxn][maxn]; int main() { int n, a, b, m; while(scanf("%d %d %d %d", &n, &a, &b, &m) != EOF) { memset(dp, 0, sizeof(dp)); for(int i = a; i <= n; i++) dp[0][i] = 1; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(j == b) { dp[i][j] += dp[i][j-1]; continue; } if(j < b) { int d = b-j; int x = j+(b-j-1)/2; dp[i][j] += dp[i-1][x]-(dp[i-1][j]-dp[i-1][j-1]); dp[i][j] %= mod; } else { int d = j-b; int x = j-(j-b-1)/2; dp[i][j] += dp[i-1][n]-dp[i-1][x-1]-(dp[i-1][j]-dp[i-1][j-1]); } dp[i][j] += dp[i][j-1]; dp[i][j] %= mod; } } //for(int j = 1; j <= n; j++) printf("%I64d\n", (dp[m][n]+mod)%mod); } return 0; }
CF 479E Riding in a Lift 前缀和 DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。