区间DP

模板
区间dp一般由小区间推出大的区间:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[1010][1010];
int main()
{
for(int i=0;i<n;i++)
 dp[i][i]=........
 
    for(int len=1;len<=n;len++)//区间长度
    {
        for(int i=0;i<n;i++)//区间起点
        {
            j=len-1+i;//区间终点
            for(int k=i;k<j;k++)//k把[i,j]分为[i,k],[k+1,j]
            {
                dp[i][j]=........
            }
        }
    }

http://acm.hdu.edu.cn/showproblem.php?pid=5115
http://blog.csdn.net/JACK_JYH/article/details/52151502

题目大意:你是一个战士现在面对,一群狼,每只狼都有一定的主动攻击力和附带攻击力。你杀死一只狼。你会受到这只狼的(主动攻击力+旁边两只狼的附带攻击力)这么多伤害~现在问你如何选择杀狼的顺序使的杀完所有狼时,自己受到的伤害最小。(提醒,狼杀死后就消失,身边原本相隔的两只狼会变成相邻,而且不需要考虑狼围城环这种情况)
输入要求:总共T组数据,每组N只狼,按顺序输入全部狼的主动攻击力和然后再按顺序输入全部狼的附带攻击力
输出要求:Case #x: y x第几组数据,y最少受到的伤害

#include<stdio.h>
#include <string.h>
#include<algorithm>
using namespace std;
#define maxn 205
int attack[maxn],assit[maxn];
int dp[maxn][maxn];
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",attack+i);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",assit+i);
        }
        assit[0]=0;
        assit[n+1]=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
                dp[i][j]=0x3f3f3f3f;
        }//合法区间设置为无穷大,其他全部设置为0
        for(int  r=1;r<=n;r++)
        {
            for(int i=1;i<=n-r+1;i++)
            {
                int j=i+r-1;
                for(int k=i;k<=j;k++)//设k为最后一只被杀死的狼
                {
                    dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+attack[k]+assit[i-1]+assit[j+1]);
                }
            }
        }
        printf("Case #%d: %d\n",cas,dp[1][n]);
    }
}

http://acm.hdu.edu.cn/showproblem.php?pid=5900
http://www.cnblogs.com/littlepear/p/5886036.html

题意:给n个数有key和val,相邻的并且key不互质的两个数可以消去并得到val,问最大价值和.
题解:状态转移有两个来源,第一个是假若一个区间[i,j]里面的物品被抽光之后,而且key[i-1]和key[j+1]满足题目条件的话,那么answer[i-1][i+1]=max(answer[i][j]+value[i]+value[j],answer[i][j]).假若在区间里面还剩下几个不能被抽走,区间[i,j]的最大值就相当于两个区间直接拼在一起喽answer[i][j]=max(answer[i][j],answer[i][k]+answer[k+1][j]).要判断区间[i,j]里的物品是否全都被抽光只需判定answer[i][j]==∑(k=i→ j)value[k]即可,为了这个的判断方便,这里特地的把value做成了前缀和的形式,方便判断

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 305
using namespace std;
typedef long long ll;
ll dp[maxn][maxn], key[maxn], val[maxn],sum[maxn];
ll gcd(ll a,ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        sum[0]=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%I64d",&key[i]);
        for(int i=1;i<=n;i++) scanf("%I64d",&val[i]),sum[i]=val[i]+sum[i-1];
        memset(dp,0,sizeof(dp));
    for(int l=2;l<=n;l++)
    {
        for(int i=1;i+l<=n+1;i++)
        {
            int j=i+l-1;
            for(int k=i;k<j;k++)
                dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
            if(gcd(key[i],key[j])>1)
            {
                if(j==i+1) dp[i][j] = val[i]+val[j];
                else if(dp[i+1][j-1]==sum[j-1]-sum[i]) dp[i][j] = max(dp[i][j],dp[i+1][j-1]+val[i]+val[j]);
            }
        }
    }
    printf("%I64d\n",dp[1][n]);
    }
}

http://acm.hdu.edu.cn/showproblem.php?pid=4283

有n个男屌丝事先按1,2,3,,,,,,n的顺序排好,每个人都有一个不开心值unhappy[i],如果第i个人第k个上台找对象,那么该屌丝男的不开心值就会为(k-1)unhappy[i],因为在他前面有k-1个人嘛,导演为了让所有男屌的总不开心值最小,搞了一个小黑屋,可以通过小黑屋来改变男屌的出场顺
。这个小黑屋是个栈,男屌的顺序是排好了的,但是可以通过入栈出栈来改变男屌的出场顺序
那么对于dp[i][j]的第i个人,就有可能第1个上场,也可以第j-i+1个上场。考虑第K个上场
即在i+1之后的K-1个人是率先上场的,那么就出现了一个子问题 dp[i+1][i+1+k-1-1]表示在第i个人之前上场的.对于第i个人,由于是第k个上场的,那么愤怒值便是val[i]
(k-1).其余的人是排在第k+1个之后出场的,也就是一个子问题dp[i+k][j],对于这个区间的人,由于排在第k+1个之后,所以整体愤怒值要加上k*(sigma(i+k--j))。

#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
#define maxn 105
using namespace std;
int dp[maxn][maxn],sum[maxn],arr[maxn];
int main()
{

    int n,t;
    scanf("%d",&t);
    for(int q=1;q<=t;q++)
    {
        scanf("%d",&n);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",arr+i);
            sum[i]=sum[i-1]+arr[i];
        }
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                dp[i][j]=0x3f3f3f;
            }
        }
        for(int r=1;r<=n;r++)
        {
            for(int i=1;i<=n-r+1;i++)
            {
                int j=i+r-1;
                for(int k=1;k<=r;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+arr[i]*(k-1)+dp[i+k][j]+(sum[j]-sum[i+k-1])*k);
                }
            }
        }
        printf("Case #%d: %d\n",q,dp[1][n]);
    }
}

石子合并 直线型

有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。

#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 205
using namespace std;
int dp[maxn][maxn],sum[maxn],arr[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            //dp[i][i]=0;
            scanf("%d",arr+i);
            sum[i]=sum[i-1]+arr[i];
        }
        memset(dp,0x3f3f3f,sizeof(dp));
        for(int i=1;i<=n;i++)
            dp[i][i]=0;
        for(int r=2;r<=n;r++)
        {
            for(int i=1;i<=n-r+1;i++)
            {
                int j=i+r-1;
                dp[i][j]=dp[i][i]+dp[i+1][j]+sum[j]-sum[i-1];
                for(int k=2;k<j;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
                }
            }
        }
        printf("%d\n",dp[1][n]);
    }
}

石子合并 环形
SCUT OJ 1207 http://www.scut.edu.cn/oj

#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 105
using namespace std;
int dp[maxn][maxn],dp2[maxn][maxn],sum[maxn][maxn],num[maxn];
int main()
{
   int n;
   while(scanf("%d",&n)!=EOF,n)
   {
       for(int i=1;i<=n;i++)
       {
           scanf("%d",num+i);
       }
       for(int i=1;i<=n;i++)
           sum[i][1]=num[i];
       for(int j=2;j<=n;j++)
       {
           for(int i=1;i<=n;i++)
               sum[i][j]=sum[i%n+1][j-1]+num[i];
       }
       for(int i=0;i<=n;i++)
           dp[i][1]=dp2[i][1]=0;
       for(int r=2;r<=n;r++)
       {
           for(int i=1;i<=n;i++)
           {
               dp2[i][r]=0;
               dp[i][r]=0x3f3f3f3f;
               for(int k=1;k<r;k++)
               {
                   dp[i][r]=min(dp[i][r],dp[i][k]+dp[(i+k-1)%n+1][r-k]+sum[i][r]);
                   dp2[i][r]=max(dp2[i][r],dp2[i][k]+dp2[(i+k-1)%n+1][r-k]+sum[i][r]);
               }
           }
       }
       int minv=0x3f3f3f3f,maxv=0;
       for(int i=1;i<=n;i++)
       {
           maxv=maxv<dp2[i][n]?dp2[i][n]:maxv;
           minv=minv>dp[i][n]?dp[i][n]:minv;
       }
       printf("%d %d\n",minv,maxv);
   }
}

最大k乘积

设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。

#include<cstdio>
#include<string.h>
#include<algorithm>
#define maxn 15
using namespace std;
int bit[maxn];
long long dp[maxn][maxn],val[maxn][maxn];
/*
num:1345
bit[1]=1,bit[2]=3,bit[3]=4,bit[4]=5;
dp[i][j]:1-i位的最大j乘积
val[s][len] :第s位开始的长度为len的数字组成的10进制数(包含s位)
dp[i][j]=max(dp[k][j-1]*val[k][j-k]) ,1<=k<i;
*/
int main(void)
{
    int n,k,num,i=0,j,m;
    long long maxv;
    char str[15];
   while(scanf("%d%d",&n,&k)!=EOF)
   {
    scanf("%s",str);
    for(i=0;i<n;i++)
        bit[i+1]=str[i]-'0';
    memset(val,0,sizeof(val));
    for(i=1;i<=n;i++)
    {
        long long ans=0;
        for(int len=1;len+i-1<=n;len++)
        {
            ans=ans*10+bit[i+len-1];
            val[i][len]=ans;
        }
    }
    memset(dp,0,sizeof(dp));
    for(i=1;i<=n;i++)
        dp[i][1]=val[1][i];
    for(i=2;i<=n;i++)
        for(j=2;j<=k;j++)
        {
            for(m=1;m<i;m++)
                dp[i][j]=max(dp[i][j],dp[m][j-1]*val[m+1][i-m]);
        }
        printf("%lld\n",dp[n][k]);
   }
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,456评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,370评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,337评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,583评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,596评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,572评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,936评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,595评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,850评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,601评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,685评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,371评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,951评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,934评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,167评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,636评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,411评论 2 342

推荐阅读更多精彩内容