区间DP

Author Avatar
Axell 8月 22, 2018
  • 在其它设备中阅读本文章

区间DP

区间DP,即一个大区间划分成若干个小的区间,从而由局部最优解得到全局最优解

通常的定义为: f[i][j]表示将i~j所能取得的最优解

与分段DP最大的区别是: 分段DP确定了分段的数量,而区间DP则可以无限制的分

例题

合法括号对

题目描述

首先我们定义“合法括号对”:

  1. 如果s=”空”, s算是合法括号对;
  2. 如果s是合法括号对,那么(s), [s] 也是合法括号对;
  3. 如果s1, s2是合法括号对,那么s1s2也是合法括号对;
  4. 上述以外都是不合法括号对;

例如,以下串是合法的: (), [], (()), ()[], ()[()]

以下串是不合法的: (, ], )(, ([)], ([(]

现在问题,给定一个串S,去掉一些字符后,使之变为合法括号对,求合法括号对最大长度是多少?

输入

输入一行,一个串S,只包含(,),[,]

输出

输出合法括号对最大长度。

样例输入

([]])

样例输出

4

提示

【样例说明】

样例输入1:

)[)(

样例输出1:

0

样例输入2:

((()))

样例输出2:

6
【数据规模和约定】

字符串长度小于等于200

思路

典型的划分DP,将原字符串拆分成多个小串进行判断

注意: 由于必须取得小范围的最优解后,才可得到大范围的最优解,所以必须先枚举步长len

代码

#include <bits/stdc++.h>
using namespace std;

int n,f[205][205];
char a[205];

bool check(int x,int y){
    return ((a[x]=='['&&a[y]==']')||(a[x]=='('&&a[y]==')'));
}

int main(){
    scanf("%s",a+1);
    n=strlen(a+1);
    for (int len=2;len<=n;len++){  //从距离为2开始枚举
        for (int i=1;i+len-1<=n;++i){
            int j=i+len-1;  //在步长为len时,确定了起点,即可确定终点
            if (check(i,j)) f[i][j]=2+f[i+1][j-1];  //这是一种特殊情况,要格外注意
            for (int k=i;k<=j-1;++k){  //枚举中间的情况
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);  //大区间分成两段求解
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

加分二叉树

题目描述

设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第j个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数
若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;
(1)tree的最高加分
(2)tree的前序遍历

输入

第1行:一个整数n(n<30),为节点个数。 
第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。 

输出

第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。 
第2行:n个用空格隔开的整数,为该树的前序遍历。 

样例输入

5
5 7 1 2 10

样例输出

145
3 1 2 4 5

提示

前序遍历:根左右

中序遍历:左根右

后序遍历:左右根

思路

典型的区间DP,先找到根节点,计算最大值

由于DFS更为方便,这里还是用DFS吧

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[35];
int f[35][35],rt[35][35];
     //f[i][j]表示[i,j]这段最优值,rt[i][j]表示[i,j]这段的根位置
int dfs(int le,int ri){
    if(le>ri) return 1; //子树为空,返回 1
    if(le==ri) {
        rt[le][ri]=le; return a[le];
    }
        //子树只有一个点,自己就是自己的根,返回这个点的值
    if(f[le][ri]!=-1) return f[le][ri]; //记忆化
    f[le][ri]=0;
    for(int i=le; i<=ri; i++){ //枚举根位置
        int t=dfs(le,i-1)*dfs(i+1,ri)+a[i];
        if(t>f[le][ri]){
            f[le][ri]=t;
            rt[le][ri]=i; //记录最优根位置
        }
    }
    return f[le][ri];
}

void print(int le,int ri){ //先序遍历打印结果
    if(le>ri) return;
    int t=rt[le][ri];
    printf("%d ",t);
    print(le,t-1); print(t+1,ri);  //打印左右子树
}

int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    for(int i=0; i<=n; i++) //记忆化搜索初始化
    for(int j=0; j<=n; j++) f[i][j]=-1;
    printf("%d\n",dfs(1,n));
    print(1,n); //打印方案
    return 0;
}

小明的喷漆计划

题目描述

小明极其喜欢涂鸦,总是在墙上涂上各种颜色的漆。现在小明得到一个任务,需要喷涂一段空白围墙,且单位长度内的颜色都是相同的。小明有一种喷涂工具,它可以给任意长度的一段墙面涂上任意颜色的漆,这样的操作计为一次操作。小明要完成这个任务,又想使得操作次数尽量少,就请你帮他解决这个问题吧。

输入

有多组输入数据。
每组包含一个长度不超过100的字符串(均由小写字母组成),代表需要涂鸦的墙面目标状态

输出

至少需要几次操作,可达到目标

样例输入

aaaaaa
fedcbaabcdef
aaabbbbb
aaabbbaaa

样例输出

1
6
2
2

思路

分段求解,如果两头的颜色一样,则可以一起喷

代码

#include<bits/stdc++.h>
using namespace std;
int f[205][205];
char s[205];
void solve(){
    int n=strlen(s+1);
    for(int i=0; i<=n; i++){ //数组数据初始化
        for(int j=0; j<=n; j++)
            if(i==j) f[i][j]=1;
            else f[i][j]=1e9;
    }
    for(int len=2; len<=n; len++){ //枚举长度
        for(int le=1; le+len-1<=n; le++){
            int ri=le+len-1; //[le,ri]枚举分割点 k
            for(int k=le; k<ri; k++){
                if(s[le]!=s[ri])
                    f[le][ri]=min(f[le][ri], f[le][k]+f[k+1][ri]);
                else //如果两端点相等,可以少涂一次(注意: 不要像第一题一样做)
                    f[le][ri]=min(f[le][ri], f[le][k]+f[k+1][ri]-1);
            }
        }
    }
    printf("%d\n",f[1][n]);
}
int main(){
    while(scanf("%s",s+1) != EOF) solve();
    return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/15/