USACO2010DEC Treasure Chest 藏宝箱

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Fri Sep 21 16:30:05 CST 2018

In Category: NoCategory

Description：

给一个序列，每次只能从两边拿数，两个人轮流操作，问先手最大得分。

$1\le n \le 5000$

Solution：

裸区间 $DP$ ，方程为 $\begin{align}f[l][r]=\sum_{i=l}^ra[i]-\min(f[i+1][j],f[i][j-1])\end{align}$ 。

但是这样会爆空间，所以按长度划分阶段，压成一维。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 5001

int s[MAXN];

int f[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&s[i]);

	for(int i = 1;i <= n;++i)f[i] = s[i];

	for(int i = 1;i <= n;++i)s[i] = s[i - 1] + s[i];

	for(int l = 2;l <= n;++l)

	{

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

		{

			int j = i + l - 1;

			f[i] = s[j] - s[i - 1] - min(f[i],f[i + 1]);

		}

	}

	cout << f[1] << endl;

	return 0;

}

In tag: DP-区间DP

wjh15101051