1392 合并傻子

1392 合并傻子 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond 

 

题目描述 Description

在一个园形操场的四周站着N个傻子,现要将傻子有次序地合并成一堆.规定每次只能选相邻的2个傻子合并成新的一个傻子，并将新的一个傻子的RP数，记为该次合并的RP数。
将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’

输入描述 Input Description

数据的第1行试正整数n和m(1≤N≤100,m在longint范围之内）表示有N个傻子.第2行有N个数,分别表示合并每个傻子的所掉的RP数

输出描述 Output Description

输出文件仅一行包含一个句子表示钟某人说的话。

样例输入 Sample Input

4 -9999
4 4 5 9

样例输出 Sample Output

I am..Sha...X

数据范围及提示 Data Size & Hint

出题人不告诉你是1S

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 110;

int num[N],s[N];
int f[N][N];
int n,m,maxn,minn;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&num[i]);
        s[i]=s[i-1]+num[i];
    }
    for(int i=n-1;i>=1;--i)
        for(int j=i+1;j<=n;++j)
            for(int k=i;k<=j-1;++k)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
    maxn=f[1][n];
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;++i) f[i][i] = 0 ;
    for(int i=n-1;i>=1;--i)
        for(int j=1;j<=n;++j)
            for(int k=i;k<=j-1;++k)
                f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
    minn = f[1][n];
    if(m>maxn)cout<<"It is easy";
    else if( m< minn) cout<<"I am..Sha...X";
    else cout<<"I will go to play WarIII";
    return 0;
}