区间dp(入门题)

时间:2023-12-20 08:21:32

区间dp:顾名思义就是在区间上进行动态规划,通过合并小区间求解一段区间上的最优解。

常见模板:

for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=be;j<en;j++){//割点
dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+割点代价);(max也可以)
}
}
}

  

http://www.51nod.com/Challenge/Problem.html#!#problemId=1021

1021 石子归并

  1. 1 秒
  2. 131,072 KB
  3. 20 分
  4. 3 级题
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如: 1 2 3 4,有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
括号里面为总代价可以看出,第一种方法的代价最低,现在给出n堆石子的数量,计算最小合并代价。

收起

输入

第1行:N(2 <= N <= 100)
第2 - N + 1:N堆石子的数量(1 <= A[i] <= 10000)

输出

输出最小合并代价

输入样例

4
1
2
3
4

输出样例

19
解题思路:很明显割点代价为前缀和:sum【en】-sum【be-1】//en为该区间的终点,be为起点
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ri register int
typedef long long ll; inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
inline void output(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch=='-'){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
x=x*f;
}
const int maxn=105;
ll dp[maxn][maxn];
ll sum[maxn];
ll a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[i+1]=sum[i]+a[i];
}
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
dp[i][j]=1e18;
}
}
for(int i=0;i<maxn;i++){
dp[i][i]=0;
}
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=be;j<en;j++){//割点
dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1]);
}
}
}
cout<<dp[1][n];
return 0;
}

  四边形不等式优化:

我们可以知道,没有优化的区间dp时间复杂度为O(n^3),我们可以使用四边形不等式优化时间复杂度为O(n^2)。

这里直接给出四边形不等式的定理:

区间包含性:如果i<=j<m<=n,则满足w【j】【m】<=w【i】【n】

四边形不等式:如果i<=j<m<=n,满足w【i】【m】+w【j】【n】<=w【i】【n】+w【j】【m】(交叉小于包含)

我们假设w函数为割点代价同时满足区间包含性和四边形不等式,那么dp函数也满足四边形不等式。

我们定义m【i】【j】为dp【i】【j】取得最优解时候的割点的坐标

此时有:如果dp满足四边形不等式,有m【i】【j】<=m【i】【j+1】<=m【i+1】【j+1】

关于该定理的证明,有兴趣的可以看这篇博客:点击

接下来用四边形不等式来优化上一道题。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define ri register int
typedef long long ll; inline ll gcd(ll i,ll j){
return j==0?i:gcd(j,i%j);
}
inline ll lcm(ll i,ll j){
return i/gcd(i,j)*j;
}
inline void output(int x){
if(x==0){putchar(48);return;}
int len=0,dg[20];
while(x>0){dg[++len]=x%10;x/=10;}
for(int i=len;i>=1;i--)putchar(dg[i]+48);
}
inline void read(int &x){
char ch=x=0;
int f=1;
while(!isdigit(ch)){
ch=getchar();
if(ch=='-'){
f=-1;
}
}
while(isdigit(ch))
x=x*10+ch-'0',ch=getchar();
x=x*f;
}
const int maxn=105;
ll dp[maxn][maxn];
ll sum[maxn];
ll a[maxn];
ll m[maxn][maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum[i+1]=sum[i]+a[i];
}
for(int i=0;i<maxn;i++){
for(int j=0;j<maxn;j++){
dp[i][j]=1e18;
}
}
for(int i=0;i<maxn;i++){
dp[i][i]=0;
m[i][i]=i;
}
for(int len=1;len<n;len++){//区间长度
for(int be=1;be+len<=n;be++){//起点
int en=be+len;//终点
for(int j=m[be][en-1];j<=m[be+1][en];j++){//割点 割点区间长度为en-be-1,dp区间为en-be,所以直接调用即可
// dp[be][en]=min(dp[be][en],dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1]);
if(dp[be][en]>=(dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1])){
dp[be][en]=dp[be][j]+dp[j+1][en]+sum[en]-sum[be-1];
m[be][en]=j;
}
}
}
}
cout<<dp[1][n];
return 0;
}

  

hdu2476

String painter

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7155    Accepted Submission(s): 3464

Problem Description
There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?
Input
Input contains multiple cases. Each case consists of two lines:
The first line contains string A.
The second line contains string B.
The length of both strings will not be greater than 100.
Output
A single line contains one integer representing the answer.
Sample Input
zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd
Sample Output
6
7
题目大意:
给出两个长度相同的字符串st1,st2,每次可以操作字符串st1内的一段区间,使其变成相同的字符,问,最少可以操作多少次,使得字符串st1与st2相等。
因为字符串st1中某个位置的字符与st2相同,所以直接dp可能很复杂。所以我们可以先假设st1每个位置的字符都与st2不同,此时我们可以定义某个状态dp【i】【j】为区间【i,j】所需的最少操作次数,
我们可以先:dp【i】【j】=dp【i+1】【j】+1,然后该区间的割点为k=【i+1,j】,if(st2【i】==st2【k】)dp【i】【j】=min(dp【i】【j】,dp【i+1】【k】+dp【k+1】【j】),因为st1此区间的字符st2不同,所以我们可以把第i号和第k同时操作。
之后,我们就可以开始考虑st1,st2某些位置可能相同的情况了。首先定义ans【i】,意为前k和字符所需要的最少操作数。
if(st1【i】==st2【i】)ans【i】=ans【i-1】;否则枚举此区间的割点,k,ans【i】=min(ans【k】+dp【k+1】【j】,dp【i】【j】),最后答案即为ans【n】。
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int dp[maxn][maxn];
char ch[maxn],ch1[maxn];
int ss[maxn];
int main(){
while(~scanf("%s%s",ch+,ch1+)){
int len=strlen(ch+);
// printf("%s %s",ch+1,ch1+1);
memset(dp,,sizeof(dp));
for(int i=;i<=len;i++){
dp[i][i]=;
}
for(int l=;l<=len;l++){
for(int be=;be+l<=len;be++){
int en=be+l;
dp[be][en]=dp[be+][en]+;
for(int k=be+;k<=en;k++){
if(ch1[be]==ch1[k])dp[be][en]=min(dp[be+][k]+dp[k+][en],dp[be][en]);
}
}
}
for(int i=;i<=len;i++){
if(ch[i]==ch1[i])
ss[i]=ss[i-];
else{
ss[i]=dp[][i];
for(int k=;k<i;k++){
ss[i]=min(ss[i],ss[k]+dp[k+][i]);
}
}
}
// for(int i=1;i<=len;i++)
printf("%d\n",ss[len]);
}
return ;
}