<问题分析>
先将题目中的还变成链，把环截断，复制一份放在后面形成一个两倍的链，max[i][j]表示从i到j最大得分，同理有min(i,j)，sum(i) 表示到i的石子串的总数量。
状态转移方程max[i][j]=max{max[i][k]+max[k+1][j]}+sum[j]-sum[i-1]
min[i][j]=min{min[i][k]+min[k+1][j]}+sum[j]-sum[i-1]
1 #include <stdio.h> 2 3 int main() 4 { 5 int i,j,k,tag1,tag2,n,v[202],sum[202],max[202][202],min[202][202]; 6 scanf("%d",&n); 7 for(i=1;i<=n;i++) 8 { 9 scanf("%d",&v[i]); 10 v[i+n]=v[i]; 11 } 12 sum[0]=0; 13 for(i=1;i<=2*n;i++) 14 { max[i][i]=0;min[i][i]=0;sum[i]=sum[i-1]+v[i];} 15 for(i=1;i<=n-1;i++) 16 { 17 for(j=1;j<2*n-i;j++) 18 { 19 tag1=0; 20 tag2=10000000; 21 for(k=j;k<j+i;k++) 22 { 23 if(max[j][k]+max[k+1][j+i]>tag1) 24 { 25 tag1=max[j][k]+max[k+1][j+i]; 26 } 27 if(min[j][k]+min[k+1][j+1]<tag2) 28 { 29 tag2=min[j][k]+min[k+1][j+i]; 30 } 31 } 32 max[j][i+j]=tag1+sum[j+i]-sum[j-1]; 33 min[j][i+j]=tag2+sum[j+i]-sum[j-1]; 34 } 35 } 36 tag1=max[1][n]; 37 tag2=min[1][n]; 38 for(i=2;i<=n;i++) 39 { 40 if(max[i][i+n-1]>tag1) 41 tag1=max[i][i+n-1]; 42 if(min[i][i+n-1]<tag2) 43 tag2=min[i][i+n-1]; 44 } 45 printf("%d %d",tag2,tag1); 46 while(true); 47 return 0; 48 }