洛谷 P2734 [USACO3.3]游戏 A Game

洛谷 P2734 [USACO3.3]游戏 A Game

Description

原题链接

Solution

今天集训讲了博弈论，于是在洛谷发现了这道题，但是并不知道为什么有博弈论的标签QWQ。

这明明是道 (区间dp) 好不好啊喂。

一道比较基础的区间 (dp)。

我们设 (f[i][j]) 表示取完 (i) ~ (j) 之间的物品，先手能获得的最大分数。

那么后手得分就是 (n - f[i][j])。

注意到两人只能从两边取，那么我们转移就更简单了，连断点都不需要枚举。

先手可能取 (i)，也可能取 (j)。

转移方程： $f[i][j] = max((sum[j] - sum[i - 1]) - f[i + 1][j] + a[i], (sum[j] - sum[i - 1]) - f[i][j - 1] + a[j]) $

这里的 (a[i]) 和 (a[j]) 可以在输入时，当作初始值赋进去。

(sum[i]：) 前缀和，表示 1 ~ (i) 物品的数字和。

Code

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 110;
int n;
int a, f[N][N], sum[N];

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a);
		sum[i] = sum[i - 1] + a;
		f[i][i] = a;
	}
	for(int len = 2; len <= n; len++)
	 	for(int i = 1; i + len - 1 <= n; i++){
	 		int j = i + len - 1;
	 		f[i][j] = max((sum[j] - sum[i - 1]) - f[i + 1][j], (sum[j] - sum[i - 1]) - f[i][j - 1]);
	 	}
	printf("%d %d
", f[1][n], sum[n] - f[1][n]);
	return 0;
}

End