HDU 6199 DP 滚动数组

强行卡内存

这题在CF上好像有道极相似的题

可以想到状态设计为dp[f][i][k]表示f在取完i-1时，此时可以取k个或k+1个的状态下的最大值。之前以为n是1e5，自己想不到怎么设计状态真的辣鸡，把题目扔给队友写，实际上n是1e4，k就算不断递增最大也只有200左右，实际上是开的下的。

由于最终局面下的最优决策是固定的，所以从后往前转移。

但是人家说本来题目就too simple了，觉得你这样申请空间还是太naive，会给你MLE。

可以注意到状态i只由i+k+1或i+k转移，k范围是200左右，那么实际上对于一个i只要保存它的临近的k大小的空间就可以完成转移了，也就是滚动数组。

/** @Date    : 2017-09-11 17:20:25

  * @FileName: HDU 6199 1006 DP.cpp

  * @Platform: Windows

  * @Author  : Lweleth ([email protected])

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 2e4+20;

const double eps = 1e-8;

int dp[2][243][243];

int sum[N];

int main()

{

	int T;

	cin >> T;

	while(T--)

	{

		int n;

		scanf("%d", &n);

		sum[0] = 0;

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

		{

			scanf("%d", sum + i);

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

		}

		MMF(dp);

		for(int i = n; i > 0; i--)//0大

		{

			for(int k = 220; k > 0; k--)

			{

				if(i + k <= n)

				{

					dp[0][i%243][k] = max(dp[1][(i + k)%243][k], dp[1][(i + k + 1)%243][k + 1]+sum[i+k]-sum[i+k-1]);

					dp[1][i%243][k] = min(dp[0][(i + k)%243][k], dp[0][(i + k + 1)%243][k + 1]-sum[i+k]+sum[i+k-1]);

				}

				else if(i + k == n + 1)

				{

					dp[0][i%243][k] = dp[1][(i + k)%243][k];

					dp[1][i%243][k] = dp[0][(i + k)%243][k];

				}

				if(i + k <= n + 1)

				{

					dp[0][i%243][k] += (sum[i + k - 1]-sum[i - 1]);

					dp[1][i%243][k] -= (sum[i + k - 1]-sum[i - 1]);

				}

			}

			//cout << dp[0][i][1] << endl;

		}

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

	}

    return 0;

}