Tyvj P1062 合并傻子

背景 从前有一堆傻子，钟某人要合并他们~ 但是，合并傻子是要掉RP的…… 描述 在一个园形操场的四周站着N个傻子,现要将傻子有次序地合并成一堆.规定每次只能选相邻的2个傻子合并成新的一个傻子，并将新的一个傻子的RP数，记为该次合并的RP数。 （合并方法与NOI1999石子合并（本题库的沙子合并）相同，请大家参考上题合并方法） 将N个傻子合并成1个的最小RP数为RPn和最大RP数为RPx. 钟某人要合并他们，钟某人现在的RP为m,但是他要小心…. if m>RPx then 钟某人能很轻松的合并他们，并说出 ‘It is easy’ else if m < RPn 钟某人很担心，因为他必然由此变成一个沙茶，这时他要说：‘I am..Sha…X’（以便提升RP） else 钟某人仍然担心自己可能成为一个沙茶，所以他要金蝉脱壳说：‘I will go to play WarIII’ 输入格式 数据的第1行试正整数n和m(1≤N≤100,m在longint范围之内）表示有N个傻子.第2行有N个数,分别表示合并每个傻子的所掉的RP数 输出格式 输出文件仅一行包含一个句子表示钟某人说的话。 测试样例1 输入 4 -9999 4 4 5 9 输出 I am..Sha…X 备注 傻子+傻子=?

---

区间动规，与石子合并一样。

---

#include<iostream> #include<cstring> #include<climits> #include<cstdio> using namespace std; int n,m,mx,mn=INT_MAX,a[201],fn[201][201],fx[201][201]; bool flg1,flg2; int main() { scanf("%d%d",&n,&m); int x; for(int i=1;i<=n;i++) { scanf("%d",&x); a[i]=a[i-1]+x; } for(int i=1;i<=n-1;i++) a[i+n]=a[i]+a[n]; memset(fn,0x3f,sizeof(fn)); for(int i=1;i<=2*n-1;i++) fn[i][i]=0; for(int i=2;i<=n;i++) for(int j=1;j<=2*n-i;j++) for(int k=j+1;k<=i+j-1;k++) { fx[j][i+j-1]=max(fx[j][i+j-1],fx[j][k-1]+fx[k][i+j-1]+a[i+j-1]-a[j-1]); fn[j][i+j-1]=min(fn[j][i+j-1],fn[j][k-1]+fn[k][i+j-1]+a[i+j-1]-a[j-1]); if(i==n) { mn=min(mn,fn[j][i+j-1]); mx=max(mx,fx[j][i+j-1]); } } if(m>mx) printf("It is easy\n"); else if(m<mn) printf("I am..Sha...X\n"); else printf("I will go to play WarIII\n"); return 0; }