洛谷p2964 其中一种常见的博弈论的dp方法

在之前，我写dp看见题目说两个人都足够聪明，然后他们进行一些操作，求某些人的最大利益，我完全不知道怎么去设计dp的方法，然后我接触了一道题，看了题解
洛谷p2734
这道题的dp方法和现在这道题其实在设计思路上面是一样。
我不知道现在是谁在取数字，但是我就是要为现在这个取数字的人谋取最大利益这个思想在博弈论的dp是很关键的。
回到原题，一开始的玩家可以取k个币，下一个人只能取小于等于k*2个
我们这么设计状态f[i][j], 表示现在在i这个币的位置，现在要拿的这个人拿了j个币后，这个人获得的总权值。
既然我们设计的是总权值，那么就不能从i= 1开始转移，要从后面开始向前面转，这样回到1的时候就是第一个人拿的总权值。
我们来尝试转移这个状态，f[i][j]很明显，你现在这个人就是拿了j个币，那么下一个人只能拿[1，j * 2]个币。也就是，如何达到f[i][j]最大？sum表示的是前缀和，那么从[i,n]的权就是sum[n] - sum[i-1]，然后下一个人拿的权是f[i+j][1, j * 2]里面最大的，为什么是最大的？因为第二个人也是最聪明的，他会选择最大的那个总权值，那么很明显，转移方程就是
maxf[i][j]表示f[i][1到n]的最大值

f[i][j] = sum[n] - sum[i - 1] - maxf[i + j][min(j * 2 ,n)];

这里唯一的难点就是要考虑到第二个人也是最聪明的，你-的数字必须是可选择的数字里面最大的。
这样从后晚前dp最终max（f[1][1],f[1][2]）就是答案，代码就是


int n, sum[max_], f[max_][max_],maxf[max_][max_];
int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + read();
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= n; j++) {
			//现在这个人拿的时候到了第i枚币，你可以拿j没
			if (i + j - 1 <= n) {
				f[i][j] = sum[n] - sum[i - 1] - maxf[i + j][min(j * 2 ,n)];
			}
			else 
				break;
		}
		for (int j = 1; j <= n; j++) {
			maxf[i][j] = max(maxf[i][j - 1], f[i][j]);
		}
	}
	int ans = max(f[1][1], f[1][2]);
	cout << ans;
	return 0;
}

但是这样过不去，为什么？因为MLE，数组开太多了，我们就在考虑化简一下，少些数组，我们观察可得可以吧maxf和f融合在一起写就好了，这样就可以少掉个f，最终代码，（其实可以不需要额外的循环来维护maxf，在一开始填这个数字的时候就可以维护了，但是由于我上一份代码只需要吧f改成fmax就可以AC， ~~我就懒得写了~~ ）

int n, sum[max_],maxf[max_][max_];
int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + read();
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= n; j++) {
			//现在这个人拿的时候到了第i枚币，你可以拿j没
			if (i + j - 1 <= n) {
				maxf[i][j] = sum[n] - sum[i - 1] - maxf[i + j][min(j * 2 ,n)];
			}
			else 
				break;
		}
		for (int j = 1; j <= n; j++) {
			maxf[i][j] = max(maxf[i][j - 1], maxf[i][j]);
		}
	}
	int ans = max(maxf[1][1], maxf[1][2]);
	cout << ans;
	return 0;
}

也就是把所有的f改成fmax，这道题主要是要学习最主要的思想！！！**去dp当前这个人的最大可得权值，你不关心现在拿的这个人是谁！！！**如果这道题是指询问第二个人的权呢？你dp出第一个人的权去减到总权就是第二个人的！这就是在开头我给出的第二个链接的题目的方法。

洛谷p2964 其中一种常见的博弈论的dp方法

全站热榜