洛谷 [P2964] 硬币的游戏

博弈论+dp

依旧是博弈论的壳子，但问的是最大值，所以要dp

设 dp[i][j] 表示该取 i 号硬币，上一次取了 j 个的先手能取的最大值，

因为每次从小到大枚举复杂度太高，所以我们要从 dp[i][i - 1] 转移，每次新加两个状态即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int MAXN = 2030;

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 n, num[MAXN], pre[MAXN], dp[MAXN][MAXN];

int main() {

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

	n = init();

	for(int i = n ; i >= 1 ; i--) {

		num[i] = init();

	}

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

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

	}

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

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

			dp[i][j] = dp[i][j - 1];

			int k = j * 2 - 1;

			if(i >= k) dp[i][j] = max(dp[i][j], pre[i] - dp[i - k][k]);

			k++;

			if(i >= k) dp[i][j] = max(dp[i][j], pre[i] - dp[i - k][k]);

		}

	}

	cout<<dp[n][1]<<endl;

	fclose(stdin);

	return 0;

}

巴特西

洛谷 [P2964] 硬币的游戏

博弈论+dp

最新文章

热门文章