首页 > 代码库 > Codeforces 712 D. Memory and Scores (DP+滚动数组+前缀和优化)
Codeforces 712 D. Memory and Scores (DP+滚动数组+前缀和优化)
题目链接：http://codeforces.com/contest/712/problem/D
A初始有一个分数a，B初始有一个分数b，有t轮比赛，每次比赛都可以取[-k, k]之间的数，问你最后A比B大的情况有多少种。
dpA[i][j]表示第i轮获得j分的情况数。因为第i轮只和第i-1轮有关，所以这里i用滚动数组优化。
要是普通做法3个for就会超时，所以要用前缀和优化，dpA[i][j]可以由一段连续的dp[i - 1][x]转移过来，所以用sumA数组存取dp[i - 1][x]的前缀和。就可以省去一个for。
B同理。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 2e5 + 205;17 LL dp[2][N], mod = 1e9 + 7, sum[N], dpA[2][N], sumA[N];18 19 int main()20 {21 int a, b, k, t;22 scanf("%d %d %d %d", &a, &b, &k, &t);23 a += 1e5, b += 1e5;24 dp[0][b] = 1;25 dpA[0][a] = 1;26 sum[b] = 1, sumA[a] = 1;27 for(int i = 1; i <= t; ++i) {28 for(int j = 1; j < N; ++j) {29 dp[i%2][j] = dpA[i%2][j] = 0;30 }31 for(int j = -k*i; j <= k*i; ++j) {32 int l = max(-k*(i - 1), j - k), r = min(k*(i - 1), j + k);33 dp[i % 2][b + j] = ((sum[r + b] - sum[l - 1 + b] + dp[i % 2][b + j]) % mod + mod) % mod;34 dpA[i % 2][a + j] = ((sumA[r + a] - sumA[l - 1 + a] + dpA[i % 2][a + j]) % mod + mod) % mod;35 }36 for(int j = 1; j < N; ++j) { //在每轮中sum都会重新更新37 sum[j] = (sum[j - 1] + dp[i % 2][j]) % mod;38 sumA[j] = (sumA[j - 1] + dpA[i % 2][j]) % mod;39 }40 }41 LL ans = 0;42 for(int i = 1; i < N; ++i) {43 ans = (ans + sum[i - 1]*dpA[t % 2][i] % mod) % mod;44 }45 printf("%lld\n", ans);46 return 0;47 }
Codeforces 712 D. Memory and Scores (DP+滚动数组+前缀和优化)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。