BZOJ 2101: [Usaco2010 Dec]Treasure Chest 藏宝箱(这是我写过最骚气的dp!)

题目描述

贝西和邦妮找到了一个藏宝箱,里面都是金币! 
但是身为两头牛,她们不能到商店里把金币换成好吃的东西,于是她们只能用这些金币来玩游戏了。  
 藏宝箱里一共有N枚金币,第i枚金币的价值是Ci。贝西和邦妮把金币排成一条直线,她们轮流取金币,看谁取到的钱最多。贝西先取,每次只能取一枚金币,而且只能选择取直线两头的金币,不能取走中间的金币。 
当所有金币取完之后,游戏就结束了。 贝西和邦妮都是非常聪明的,她们会采用最好的办法让自己取到的金币最多。 
请帮助贝西计算一下,她能拿到多少钱? 

输入

第1行:单个整数N,表示硬币的数量,1<=N≤5000  
第2~N+1行:第i+1行有一个整数Ci,代表第i块硬币的价值,1≤Ci≤5000 

输出

输出一行:单个整数,表示如果双方都按最优策略玩游戏,先手可以拿到的最大价值。

样例输入 Copy

4
30
25
10
35

样例输出 Copy

60

空间限制:64MB,n<=5000,开5000*5000的二维数组需要94MB的内存!!
题解:
首先,应该是一个n方(时间复杂度)的dp,看到空间果断是要压掉一维的。
n方的方程式:

f[i,j]=sum[i,j]-min(f[i+1,j],f[i,j-1]).
//强行解释:
f[i][j]表示从i到j取得最大值。
sum为前缀和,sum[i][j]就是i到j的累加和

 

注意了!!!!(划重点,敲黑板)这个方程式我一开始没有理解(不是最大值吗,为什么是min???(黑人问号脸)),后来看了一段时间,才发现:
这个方程式的意思是:贝西只能取左端点或者右端点的硬币,拿完了左或者右,剩下的i+1~j或者i~j-1个金币就由邦妮取了,min就是在贝西拿完金币之后,邦妮的“最大值”。
转化的思想:先手最优相当于后手最劣。以为题目并没有要求后手也是最优,所以我们就把邦妮的智商手动变低,找最大值得相对最小值,这时候贝西拿的就是最优了。(真骚气)

解决了方程的问题,来着手解决空间的问题。首先,没有卡时间,卡了空间,这就很难受了,只能努力用滚动数组来滚掉一维。

但是,当前的状态并不允许我们滚动。

因为以前写过一题类似的题目(貌似是区间dp),借鉴一下区间的板子,改变一下状态的表示方法(不是改变状态):

 

f[i,len]=sum[i,i+len]-min(f[i+1,len-1],f[i,len-1]).

f[i][len]表示从i开始,len长度(i+len=j)的最大值

不枚举j,而是枚举i(起点)和区间长度,但是时间复杂度却没有变。

这时候就能看出,第二维根本没有用(前后一样的)

于是就可以开心快落地滚掉一维了

代码短小精悍:

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5005;
 4 int n;
 5 int sum[maxn];
 6 int dp[maxn];
 7 
 8 int main()
 9 {
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)
12     {
13         scanf("%d",&dp[i]);
14         sum[i]=sum[i-1]+dp[i];
15     }
16     for(int len=1;len<=n;len++)
17     {
18         for(int i=1;i+len<=n;i++)
19         {
20             dp[i]=sum[i+len]-sum[i-1]-min(dp[i],dp[i+1]);
21             
22         }
23     }
24     printf("%d",dp[1]);
25     return 0;
26 }

 

慢着!你以为到这就结束了?

↘         ↓          ↙

→    传送门     ←

↗         ↑          ↖

(完)

 

上一篇:D. Treasure Island


下一篇:HDU4091:Zombie’s Treasure Chest (分类-数学)