洛谷 [P2734] 游戏

博弈论+区间dp

有博弈论吗？大约只有一个博弈论的壳子

设 dp[i][j] 表示区间 i ~ j 先手最多能取多少，

它可以由 i ~ j - 1 与 i + 1 ~ j 来转移，

等于上述两个区间中后手的最大值 + 选的数

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 105;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

int num[MAXN], n, pre[MAXN], dp[MAXN][MAXN];

int main() {

	freopen("in.txt", "r", stdin);

	n = init();

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

		num[i] = init();

		pre[i] = pre[i - 1] + num[i];

		dp[i][i] = num[i];

	}

	for(int k = 2 ; k <= n ; k++) {

		for(int i = 1 ; i + k - 1 <= n ; i++) {

			int j = i + k - 1;

			dp[i][j] = max(pre[j - 1] - pre[i - 1] - dp[i][j - 1] + num[j],

				pre[j] - pre[i] - dp[i + 1][j] + num[i]);

		}

	}

	printf("%d %d\n",dp[1][n], pre[n] - dp[1][n]);

	fclose(stdin);

	return 0;

}

巴特西

洛谷 [P2734] 游戏

博弈论+区间dp

最新文章

热门文章