「JoyOI1062」合并傻子
题目描述
在一个园形操场的四周站着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数
输出
输出文件仅一行包含一个句子表示钟某人说的话。
样例输入
4 -9999 4 4 5 9
样例输出
I am..Sha…X
提示
傻子+傻子=?
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<iostream> #include<cstring> using namespace std; int mx[1001][1001]={0},mn[1001][1001]; int s[1001]; int n,m,i,j,k,l,x; int rpn=999999; int rpx=-999999; int main() { cin>>n>>m; for(i=1;i<=n;i++) { cin>>x; s[i]=s[i-1]+x; } for(i=n+1;i<=2*n;i++){ s[i]=s[i-n]+s[n];} memset(mn,127/3,sizeof(mn)); for(i=1;i<=2*n;i++)mn[i][i]=0; for(l=1;l<=n;l++) for(i=1;i<=2*n-l;i++) { j=i+l; for(k=i;k<j;k++) { mn[i][j]=min(mn[i][j],mn[i][k]+mn[k+1][j]+s[j]-s[i-1]); mx[i][j]=max(mx[i][j],mx[i][k]+mx[k+1][j]+s[j]-s[i-1]); } } for(i=1;i<=n;i++) { rpn=min(rpn,mn[i][i+n-1]); rpx=max(rpx,mx[i][i+n-1]); } if(m<rpn)cout<<"I am..Sha...X"; else if(m>rpx)cout<<"It is easy"; else cout<<"I will go to play WarIII"; return 0; } |
Subscribe
计数器 9785292
OI 课件=>
OI 课件=>