合并傻子//区间dp-白红宇

合并傻子//区间dp

阅读量：7168 次

发布时间：2019-06-29

本文共 1582 字，大约阅读时间需要 5 分钟。

P1062 合并傻子

时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

从前有一堆傻子，钟某人要合并他们~

但是，合并傻子是要掉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
       
        #include
        
         #include
         
          #include
          
           #define inf 0x7fffffffusing namespace std;int a,sum[305],n;int f1[305][305],f2[305][305];long int m;int dpn(int l,int r)//min{    if(f1[l][r]!=-1)return f1[l][r];    if(l==r)return 0;    int ans=inf;    for(int i=l;i
           
            >n>>m;     memset(f1,-1,sizeof(f1));    memset(f2,-1,sizeof(f2));    for(int i=1;i<=n;i++)     {         cin>>a;         sum[i]=sum[i-1]+a;     }     if(m
            
             dpx(1,n))puts("It is easy"); else puts("I will go to play WarIII"); return 0;}

View Code

第一次忘了开俩数组或者来清零搞一搞导致输出一直很奇怪。后来改开俩数组秒过。

区间dp

用f(i,j)表示将 i 到 j 一段合并所需要的最小代价，枚举中间的断点K转移

sum[i]表示前i个沙子的质量和，那么(l,r)的质量就是sum[r]-sum[l-1]

即

f(i,k)+f(k+1,j)}

转载于:https://www.cnblogs.com/gc812/p/5790003.html

你可能感兴趣的文章