USACO3.3 A Game【区间dp】

这道题也是一道非常有意思的区间$dp$，和在纪中的这道题有点像：取数游戏（除了取数规则其它好像都一样诶）

当时在纪中的时候就觉得这个$dp$非常不好想，状态定义都不是很容易想到。

但是做过一道这种题之后就要好多了。

以下才是正题：

两人都按照最优策略进行游戏的话，就可以定义状态$dp[i][j]$表示当前操作者面对（用词...有点奇怪？）的区间是$[i,j]$的最优解（最大的数的和），也就是他能够取的数是$a[i]$和a[j]的状态下的最优解。

两人都按最优策略取，取了一次之后先手变后手，所以转移：

$$dp[i][j]=max(sum[i+1][j]-dp[i+1][j]+a[i],sum[i][j-1]-dp[i][j-1]+a[j])$$

相同地，这道题也需要考虑转移时的枚举顺序，按长度从小到大枚举就可以了。

 /*

 ID: Starry21

 LANG: C++

 TASK: game1

 */

 #include<iostream>

 #include<string>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 #include<vector>

 using namespace std;

 #define N 105

 #define ll long long

 #define INF 0x3f3f3f3f

 int n;

 int a[N];

 int dp[N][N],s[N];

 int main()

 {

     freopen("game1.in","r",stdin);

     freopen("game1.out","w",stdout);

     scanf("%d",&n);

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

     {

         scanf("%d",&a[i]);

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

         dp[i][i]=a[i];

     }

     for(int len=;len<=n;len++)

         for(int i=;i<=n-len+;i++)

         {

             int j=i+len-;

             dp[i][j]=max(s[j]-s[i]-dp[i+][j]+a[i],s[j-]-s[i-]-dp[i][j-]+a[j]);

         }

     printf("%d %d\n",dp[][n],s[n]-dp[][n]);

     return ;

 }

Code

巴特西

USACO3.3 A Game【区间dp】

最新文章

热门文章