说到这题，我得感谢一下出题人的仁慈，n=100的分高达90，因为题目标算为O(1)...
我首先想到的是dp,用dp[i][j][k]表示Jack在i，Rose在j，k这个人选择接下来要走的这一步的这个状态下，Jack的金钱与Rose的金钱的差值。
如果k=0表示Jack选择，k=1Rose选择
dp方程很显然
dp[i][j][0]=max(dp[i+1][j][1]+a[i],dp[i][j-1][1]-a[j]);
dp[i][j][1]=min(dp[i+1][j][0]+a[i],dp[i][j-1][0]-a[j]);
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int t,a[10009],n,dp[7009][7009][2]; int main() { scanf("%d",&t); while (t--) { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int len=2;len<=n;len++) for (int i=1;i<=n-len+1;i++) { int j=i+len-1; dp[i][j][0]=max(dp[i+1][j][1]+a[i],dp[i][j-1][1]-a[j]); dp[i][j][1]=min(dp[i+1][j][0]+a[i],dp[i][j-1][0]-a[j]); } if (dp[1][n][0]==0) printf("tie "); else if (dp[1][n][0]>0) printf("win "); else printf("lose "); } return 0; }
然而这么写的话空间和时间都是n^2的。。。。能过90分。。
结果看了一下你会发现，假设mid=n/2+1,最后的位置可以被两人控制在mid-1,mid,和mid+1这三个位置上（如果n是奇数的话），所以只要分别计算在这几个位置上的金钱，然后分类讨论一下就好了。。。具体程序写。。。
感觉自己好弱。。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int t,sum[10009],a[10009],n,x,y,lef,righ,mid; int main() { scanf("%d",&t); while (t--) { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } mid=n/2+1;lef=sum[mid];righ=sum[n]-sum[mid-1]; if(n%2!=0) { x=lef-a[mid]-(righ+a[mid-1]);y=lef+a[mid+1]-(righ-a[mid]); if (lef>righ) { if ((x>0)||(y>0)) puts("win "); //只要中间位置为胜，左右两边有任意一个位置为胜，那么最终就能为胜。 else if ((x==0)||(y==0)) puts("tie "); else puts("lose "); } if (lef==righ) { if ((x>=0)||(y>=0)) puts("tie "); //只要有任意一边不为输，那么最终结果就为平局。 else puts("lose "); } if (lef<righ) puts("lose "); } mid=n/2+1;lef=sum[mid];righ=sum[n]-sum[mid-1]; if (n%2==0) { x=lef-a[mid]-(righ+a[mid-1]);y=lef-righ; if ((x>0)||(y>0)) puts("win "); else if ((x==0)||(y==0)) puts("tie "); else puts("lose "); } } return 0; }