hdu 6199 莱比锡互连网赛—gems gems gems(DP卡塔尔国,hdu—gems

题目链接

 

Problem Description Now there are n gems, each of which has its own value.
Alice and Bob play a game with these n gems.
They place the gems in a row and decide to take turns to take gems from
left to right. 
Alice goes first and takes 1 or 2 gems from the left. After that, on
each turn a player can take k or k+1 gems if the other player
takes k gems in the previous turn. The game
ends when there are no gems left or the current player can’t take k or k+1 gems.
Your task is to determine the difference between the total value of gems
Alice took and Bob took. Assume both players play optimally. Alice wants
to maximize the difference while Bob wants to minimize it.

 

 

Input The first line contains an integer T (1≤T≤10), the
number of the test cases. 
For each test case:
the first line contains a numbers n (1≤n≤20000);
the second line contains n numbers: V1,V2…Vn.
(−100000≤Vi≤100000)

 

 

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 1 3 2  

 

Sample Output 4     题意:将来有n块宝石排成风华正茂行,价值为v[1~n]。
未来艾丽丝和鲍伯从左至右改造取宝石,阿丽丝先取,能够取1或2个,然后鲍勃取……即便前一人取了k个,那么当前以这个人不能不取k或许k+1个宝石。(甘休条件,假诺前一人取了k个宝石,而剩余的一定量k个则结束不用取;假诺剩余k个,那么此人总得取k个卡塔 尔(阿拉伯语:قطر‎,今后阿丽丝和Bob都想获得的宝石价值和比对方尽量多,求阿丽丝获得的价值和

  • Bob获得的市场股票总值和的最大值?   思路:动态规划,定义dp[i][k][j],
    k取值0和1(0表示Iris取,1代表Bob取卡塔尔,i表示第i块宝石(1<=i<=二〇〇〇0卡塔 尔(阿拉伯语:قطر‎,j表示从第i块宝石早先向右取j块宝石(1<=j<=200,
    因为依次增加的取宝石,一个人二遍最多取200块宝石卡塔尔,所以dp[i][k][j]意味着取完i~n块宝石时(由后迈入推卡塔 尔(阿拉伯语:قطر‎,第k私人民居房从i开始向右接二连三取k个宝石多少人的价值差;
           
     其它,本题空间范围比较紧,所以供给使用滚动数组,第意气风发维设为205就可以。  
    代码如下:

    #include
    #include
    #include
    #include
    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("%dn",ans);
      }
      return 0;
    

    }

 

6199 武汉互联网赛—gems gems
gems(DP卡塔尔,hdu—gems 标题链接 Problem Description Now there are n
gems, each of which has its own value. 阿丽丝 and Bob play a game
wit…

相关文章