区间DP
区间DP
区间DP,即一个大区间划分成若干个小的区间,从而由局部最优解得到全局最优解
通常的定义为: f[i][j]表示将i~j所能取得的最优解
与分段DP最大的区别是: 分段DP确定了分段的数量,而区间DP则可以无限制的分
例题
合法括号对
题目描述
首先我们定义“合法括号对”：
- 如果s=”空”, s算是合法括号对；
- 如果s是合法括号对，那么(s), [s] 也是合法括号对；
- 如果s1, s2是合法括号对，那么s1s2也是合法括号对；
- 上述以外都是不合法括号对；
例如，以下串是合法的： (), [], (()), ()[], ()[()]
以下串是不合法的： (, ], )(, ([)], ([(]
现在问题，给定一个串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://hs-blog.axell.top/archives/15/
