一道ACM题，取数游戏,该怎么解决

一道ACM题，取数游戏
题目：http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1258
我觉得这是一个dp。player1总能win。但是WA了。我的WA码：

C/C++ code

#include<stdio.h>#define max 100000int dp[2*max][2];int data[2*max];int main(){    int N,i,a,b,j;    //freopen("in.txt","r",stdin);    scanf("%d",&N);    for(i=0;i<2*N;i++)    {        scanf("%d",&data[i]);        //dp[i][1]=dp[i][0];    }    for(i=1;i<2*N;i++)    {        for(j=0;j<2*N-i;j++)        {            a=dp[j][1]+data[i+j];            b=dp[j+1][1]+data[j];            if(a>b)            {                dp[j][0]=a;                dp[j][1]=b;            }            else            {                dp[j][0]=b;                dp[j][1]=a;            }            }            }            if(a>b)        {            printf("player1,%d",2*N);        }        else        {            printf("player1,1");        }    return 0;}

是不是我哪理解错了呢。。

[解决办法]
其实只要比较奇数位和偶数位的和就行了。
假如A先取第1个数，那么B只能取第2或者2N位数，也就是某个偶数位数，那么A可以继续取奇数位数；假如A先取奇数位数亦然。
[解决办法]
有多组数据吧,我把楼主的代码改下去提交，TLE了，最多200 0000 个数字，两个循环显然会超时的。

C/C++ code

#include<iostream>using namespace std; #define max 1000005int dp[2*max][2];int data[2*max];int main(){     int N,i,a,b,j;    //freopen("in.txt","r",stdin);    while(scanf("%d",&N)==1){ ///////////////////     for(i=0;i<2*N;i++)    {        scanf("%d",&data[i]);        //dp[i][1]=dp[i][0];    }    memset(dp,0,sizeof(dp));     for(i=1;i<2*N;i++)    {        for(j=0;j<2*N-i;j++)        {            a=dp[j][1]+data[i+j];            b=dp[j+1][1]+data[j];            if(a>b)            {                dp[j][0]=a;                dp[j][1]=b;            }            else            {                dp[j][0]=b;                dp[j][1]=a;            }            }            }            if(a>b)        {            printf("player1,%d",2*N);        }        else        {            printf("player1,1");        }    }     return 0;} 

 

查看更多 下一篇