【Tyvj1062】合并傻子

2014-04-22
竞赛题解 / 动态规划
TYVJ

描述 Description

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

（合并方法与 NOI1999 石子合并（本题库的沙子合并）相同，请大家参考上题合并方法）

将 N 个傻子合并成 1 个的最小 RP 数为 RPn 和最大 RP 数为 RPx.

钟某人要合并他们，钟某人现在的 RP 为 m, 但是他要小心….

if m>RPx then 钟某人能很轻松的合并他们，并说出 ‘It is easy’

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

输出格式 OutputFormat

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

样例输入 SampleInput

27 23398149
64348 64811 76365 69037 69815 58450 50328 87498 39255 22175 90134 69974 83631 51356 69368 30607 60040 45347 98409 80430 84084 5349 69325 1654 81508 91734 30616

样例输出 SampleOutput

I will go to play WarIII

Tyvj 1062

代码 Code

简单的动规。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x7fffffff
int f[101][101];
int a[101],sum[101];
int i,j,t,n,m,l,r,k,z,y,x,xmax,xmin;
int main()
{
    memset(f,0,sizeof(f));
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for (i=n;i>0;i--) for (j=i+1;j<=n;j++)
    {
        for (k=i+1;k<j;k++)
        {
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
        f[i][j]+=sum[j]-sum[i-1];
    }
    xmin=f[1][n];
    memset(f,0,sizeof(f));
    for (i=n;i>0;i--) for (j=i+1;j<=n;j++)
    {
        for (k=i+1;k<j;k++)
        {
            f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
        }
        f[i][j]+=sum[j]-sum[i-1];
    }
    xmax=f[1][n];
    if (m>xmax) printf("It is easy\n");
    else if (m<xmin) printf("I am..Sha...X\n");
    else printf("I will go to play WarIII");
    return 0;
}