D1. Game on Sum (Easy Version)

D1. Game on Sum (Easy Version)

tag：

• 2100
• dp 博弈game 数学
• 时间复杂度 $o(n\ast m)o(n*m)$

题意：

有$nn$次操作，博弈先手A每次操作可以枚举$0-k0-k$中任意一个实数，后手B每次可选择$++$还是$--$这个数。但+操作最少能做$mm$次。 A需要最大值，B需要最小值。A选择的实数已知，求最终结果。两人均最优操作。

思路：

本题可以说是一道经典的博弈dp题，利用博弈+数学得到一个函数规划，然后通过函数规划推出动态规划的转移方程。

首先，发挥灵感，大胆下结论，这是一道dp。我们需要做的事情就很明确，就是构建转移方程。 将$m=0m=0$和$m=nm=n$单独拉出来考虑，显然结果为$00$和$n\ast kn*k$。

一般情况就变成，对于第$ii$次操作，已经选择了$jj$次$++$，这次选择转移目标就是第$i-1i-1$次操作已经选了$jj$次$++$ 和第$i-1i-1$次操作已经选择了$j-1j-1$次$++$

转移方程就能自然写出

接下来就可以发现，这里就是一个非常典型的一次函数求极值问题。我们很显然可以得到x的最优解为(dp[i - 1][j] - dp[i - 1][j - 1] )/ 2 此时，两个值完全相同

有了转移方程，接下来就是构建dp的初始状态。我们发现，对于k的初始值讨论是没有意义的。

所有函数都是建立在一次函数之上，因此k的指数一直是1。 我们仅需用1将转移结果尽数写出，即可得到一个状态表。然后对于状态表内的值乘他所需的k即可。 这里运用了简单的打表思想，容易将人绕进坑内。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4005;
long long  dp[maxn][maxn];
const int mod = 1e9 + 7;
const int inv = 5e8 + 4;
int main() {
	int n, m, k;
	for (int i = 0; i < maxn; i++) {
		dp[i][0] = 0;
		dp[i][i] = i;
	}
	for (int i = 2; i <= maxn-5; i++) {
		for (int j = 1; j < i; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) * inv % mod;
		}
	}
	int t = 0;
	cin >> t;
	while (t--) {
		cin >> n >> m >> k;
		cout << dp[n][m] * k % mod<<"\n";
	}
 
}