Codeforces 712D DP

题意：有2个人玩游戏，他们都有个初始值a和b，游戏进行t轮，每次可以选择加上一个[-k, +k]之间的数字，问有多少种方案a的和严格大于b的和。

思路：如果不考虑多于这个条件，只是询问有多少种方案的化，这是一个数塔模型的DP，设dp[i][j]为到i位置，前面的数的和为j的方案数，直接转移即可。需要用前缀和优化。对两个人分别DP一次，然后枚举第一个人的最后的和，去找第二个人有多少个和小于它的方案。这个也需要用前缀和来优化。

代码：

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const LL mod = 1000000007;

const int maxn = 210010;

LL dp[2][110][maxn];

LL sum[2][maxn];

LL get_sum(int pos, int l, int r, int lb, int rb) {

	l = max(l, lb);

	r = min(r, rb);

	if(l > r) return 0;

	return (sum[pos][r] - sum[pos][l - 1] + mod) % mod;

}

int main() {

	int a, b, k, t;

	scanf("%d%d%d%d", &a, &b, &k, &t);

	int ed = 210000;

	dp[0][0][t * k + 1 + a] = 1;

	dp[1][0][t * k + 1 + b] = 1;

	for (int pos = 0; pos <= 1; pos++) {

		for (int i = 1; i <= t; i++) {

			for (int j = 1; j <= ed; j++)

				sum[pos][j] = (sum[pos][j - 1] + dp[pos][i - 1][j]) % mod;

			for (int j = 1; j <= ed; j++)

				dp[pos][i][j] = get_sum(pos, j - k, j + k, 1, ed);

		}

	}

	for (int pos = 0; pos <= 1; pos++) {

		for (int i = 1; i <= ed; i++)

			sum[pos][i] = (sum[pos][i - 1] + dp[pos][t][i]) % mod;

	}

	LL ans = 0;

	for (int i = a + 1; i <= a + 1 + 2 * t * k; i++) {

		ans = (ans + (dp[0][t][i] * get_sum(1, 1, i - 1, b + 1, b + 1 + 2 * t * k)) % mod) % mod;

	}

	printf("%lld\n", ans);

}

巴特西

Codeforces 712D DP

最新文章

热门文章