USACO Training3.3 A Game【区间Dp】 By cellur925

题目传送门

一股浓浓的博弈论香气...然而本蒟并不会博弈论。

开始用双端队列+假的dp水过了24pts水数据。

其实是布星的，两人都绝顶聪明会深谋远虑不像我只看眼前，所以上述算法错误。

正解：区间dp。决策有两种：从右边取或是左边。而且答案是由小部分一步步推到大部分的，所以区间dp再适合不过啦。

状态：如常。$f[i][j]$表示拿从i到j玩家1得到的最大得分。

转移方程：$f[i][j]=max(sub[j]-sub[i-1]-f[i][j-1],sub[j]-sub[i-1]-f[i+1][j])$ sub[]是前缀和数组。

　　第一个：当1拿了最右，则2拿i到j-1，剩下的归1；第二个同理。

目标：$f[1][n]$ （玩家1） $sub[n]-f[1][n]$（玩家2）

Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 
 6 int n;
 7 int a[500],sub[500];
 8 int f[500][500];
 9 
10 int main()
11 {
12     scanf("%d",&n);
13     for(int i=1;i<=n;i++)
14         scanf("%d",&a[i]),sub[i]=sub[i-1]+a[i],f[i][i]=a[i];
15     for(int i=n-1;i>=1;i--)
16         for(int j=i+1;j<=n;j++)
17             f[i][j]=max(sub[j]-sub[i-1]-f[i+1][j],sub[j]-sub[i-1]-f[i][j-1]);
18     printf("%d %d",f[1][n],sub[n]-f[1][n]);    
19     return 0;
20 }

View Code

这么水都不会，我好菜呀。。。

Update：倒序循环的原因 $f[i][j]$需要从$f[i+1][j]$转移过来...