「模拟赛20181025」御风剑术博弈论+DP简单优化

题目描述

Yasuo 和Riven对一排\(n\)个假人开始练习。斩杀第\(i\)个假人会得到\(c_i\)个精粹。双方轮流出招，他们在练习中互相学习，所以他们的剑术越来越强。基于对方上一次斩杀的假人数量\(k\)，可以斩杀掉剩余假人中位置最靠前的\([1,2k]\)范围内数量的连续假人。最初Yasuo先出招，斩杀\(1\)或\(2\)个假人。Yasuo偷偷把你叫到一边，问在双方都采取最优策略的情况下, 他最多能够获取多少精粹。

输入

第一行一个正整数\(n\)，表示假人的个数。

接下来\(n\)行，每行一个正整数\(c_i\)表示斩杀每个假人获得的精粹数。

输出

一个正整数表示 Yasuo 能够得到的最大精粹数量。

样例输入

样例输出

样例解释

Yasuo 斩\(1\)号，Riven 斩\(2\)号，Yasuo 斩\(3,4\)号，Riven 斩\(5\)号。

数据范围

对于前\(10\%\)的数据，\(n \leq 10\)

对于前\(40\%\)的数据，\(n \leq 500\)

对于\(100\%\)的数据，\(5 \leq n \leq 5000, ci \leq 10^9\)

题解

首先，吐槽题目背景，并吐槽搬题并魔改的出题人。

简单博弈论\(DP\)，几乎不怎么涉及博弈论的知识。

显然两人其实是等价的，设\(f[i][j]\)表示现在剩下末尾的\(i\)个假人，最后一刀是砍了\(j\)个假人，能得到的最大值。显然我们可以枚举下一刀砍了多少人\(k\in[1,2j]\)，\(DP\)状态的转移就会非常简单。但很遗憾，这样的复杂度是\(O(n^3)\)，并不能通过所有测试点。

考虑优化，我们把\(DP\)式子写下来吧：

\(f[i][j] = max(s[i]-f[i-k][k])\)，其中\(k\in[1,2j]\)，\(s[i]\)表示后\(i\)个人的\(c\)之和。

化一下式子：

\(f[i][j] = max(f[i][j-1],s[i]-f[i-2j][2j],s[i]-f[i-2j+1][2j-1])\)

然后就没了……

\(Code:\)

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define N 5005

#define ll long long

#define inf (1ll << 50)

template<typename Mytype>void Read(Mytype &p)

{

	p = 0;

	char c = getchar();

	for (; c < '0' || c > '9'; c = getchar());

	for (; c >= '0' && c <= '9'; c = getchar())p = p * 10 + c - '0';

}

ll s[N];

ll f[5005][5005];

int n, A[N];

int main()

{

	Read(n);

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

		Read(A[i]), s[n - i + 1] = A[i];

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

		s[i] += s[i - 1];

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

	{

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

		{

			ll ans1 = -inf, ans2 = -inf;

			if (i >= (2 * j - 1))

				ans1 = s[i] - f[i - (2 * j - 1)][2 * j - 1];

			if (i >= (2 * j))

				ans2 = s[i] - f[i - 2 * j][2 * j];

			f[i][j] = max(max(ans1, ans2), f[i][j - 1]);

		}

	}

	printf("%lld\n", f[n][1]);

}

2j