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

备注

傻子+傻子=?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

比起合并果子，我倒觉得这道题更像能量项链，把环拆开变成2*n-1的长度，然后就是区间动规了~

主要是合并果子可以用简单到爆的堆来做，根本不用动规。

#include<cstdio> #include<cstring> #define max(u,v) u>v ? u:v #define min(u,v) u<v ? u:v int n,m,x,a[1001],fmax[1001][1001],fmin[1001][1001]; int maxx=-999999999,minn=999999999; int main() { scanf("%d%d",&n,&m); memset(fmin,127,sizeof(fmin)); for(int i=1;i<=n*2;i++) fmin[i][i]=0; for(int i=1;i<=n;i++) { scanf("%d",&x); a[i]=a[i-1]+x; } for(int i=n+1;i<=2*n-1;i++) a[i]=a[i-n]+a[n]; for(int l=1;l<=n;l++) for(int i=1;i<=n-l;i++) { int j=l+i; for(int k=i;k<j;k++) { fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+a[j]-a[i-1]); fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+a[j]-a[i-1]); } } for(int i=1;i<=n;i++) { if(minn>fmin[i][i+n-1]) minn=fmin[i][i+n-1]; if(maxx<fmax[i][i+n-1]) maxx=fmax[i][i+n-1]; } if(m>maxx) printf("It is easy\n"); else if(m<minn) printf("I am..Sha...X\n"); else printf("I will go to play WarIII\n"); return 0; }