首页 > > 程序设计 > C/C++ >

hdu 6199 沈阳网络赛---gems gems gems（DP）

2018-06-17 21:56:31来源：未知阅读 ()

题目链接

Problem Description

Now there are

Input

The first line contains an integer

Output

For each test case, print a single number in a line: the difference between the total value of gems Alice took and the total value of gems Bob took.

Sample Input

1 3 2

Sample Output

题意：现在有n块宝石排成一行，价值为v[1~n]。现在Alice和Bob 从左至右轮流取宝石，Alice先取，可以取1或2个，然后Bob取……如果前一个人取了k个，那么当前这个人只能取k或者k+1个宝石。（结束条件，如果前一个人取了k个宝石，而剩下的少于k个则停止不用取；如果剩余k个，那么这个人必须取k个），现在Alice和Bob都想得到的宝石价值和比对方尽量多，求Alice得到的价值和 - Bob得到的价值和的最大值？

思路：动态规划，定义dp[i][k][j], k取值0和1（0表示Alice取，1表示Bob取），i表示第i块宝石（1<=i<=20000），j表示从第i块宝石开始向右取j块宝石（1<=j<=200, 因为递增的取宝石，一个人一次最多取200块宝石），所以dp[i][k][j]表示取完i~n块宝石时（由后向前推），第k个人从i开始向右连续取k个宝石两人的价值差；

另外，本题空间限制比较紧，所以需要使用滚动数组，第一维设为205即可。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=20005;
const int M=203;
int sum[N];
int dp[M][2][205];

int main()
{
    int T; cin>>T;
    while(T--)
    {
       sum[0]=0;
       memset(dp,0,sizeof(dp));
       int n; scanf("%d",&n);
       for(int i=1;i<=n;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
       for(int i=n;i>=1;i--)
       {
           for(int j=1;j<M;j++)
           {
               if(i+j-1>n) break;

               int tmp=sum[i+j-1]-sum[i-1], t;
               if(i+j+j<=n) t=min(dp[(i+j)%M][1][j],dp[(i+j)%M][1][j+1]);
               else if(i+j+j-1<=n) t=dp[(i+j)%M][1][j];
               else t=0;
               dp[i%M][0][j]=tmp+t;

               if(i+j+j<=n) t=max(dp[(i+j)%M][0][j],dp[(i+j)%M][0][j+1]);
               else if(i+j+j-1<=n) t=dp[(i+j)%M][0][j];
               else t=0;
               dp[i%M][1][j]=t-tmp;
           }
       }
       int ans;
       if(n>=2) ans=max(dp[1][0][1],dp[1][0][2]);
       else ans=dp[1][0][1];
       printf("%d\n",ans);
    }
    return 0;
}