题意分析

其实就是环形的式子合并

代码总览

#include<bits/stdc++.h> using namespace std; const int nmax = 255; int sum[nmax]; int a[nmax]; int dp[nmax][nmax],dp2[nmax][nmax]; int n,m; int main(){ while(scanf("%d%d",&n,&m)!=EOF){ for(int i = 1;i<=n;++i) scanf("%d",&a[i]); for(int i = n+1;i<=2*n;++i) a[i] = a[i-n]; for(int i = 1;i<=2*n;++i) sum[i] = sum[i-1] + a[i]; for(int len = 2;len<=n;++len){ for(int i = 1;i<=2*n-len+1;++i){ int j = i+len-1; dp[i][j] = 0; dp2[i][j] = 0x3f3f3f3f; for(int k = i;k<j;++k){ dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); dp2[i][j] = min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); } } } int mmax = 0,mmin = 0x3f3f3f3f; for(int i = 1;i<=n;++i){ mmax = max(mmax,dp[i][n+i-1]); mmin = min(mmin,dp2[i][n+i-1]); } if(m>mmax) printf("It is easy\n"); else if(m<mmin) printf("I am..Sha...X\n"); else printf("I will go to play WarIII\n"); } return 0; }