[学习笔记] 区间DP

2024-02-26 12:55:34

P2858 [USACO06FEB]Treats for the Cows G/S

这道题加深了我对区间DP阶段划分的理解（原来 \(f[l+1][r] , f[l][r-1]\) 是可以更新\(f[l][r]\)的！）

我们可以先想状态设 \(f[l][r]\) 表示 \(l\) 到 \(r\)​ 天的最多能得到的钱,得到：

\(f[l][r]=max(f[l][r-1]+v[r]*(n-i+1),f[l+1][r]+v[l]*(n-i+1));\)​

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
bool ed;
int v[N],ans=-1,n,f[2020][2020];
bool st,flag;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int dfs(int cnt,int l,int r){
    if(r<l) return 0;
    if(f[l][r]) return f[l][r];
    f[l][r]=max(dfs(cnt+1,l+1,r)+cnt*v[l],dfs(cnt+1,l,r-1)+cnt*v[r]);
    return f[l][r];
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) v[i]=read();
    dfs(1,1,n);
    cout<<f[1][n]<<endl;
    return 0;
}

DP:

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
bool ed;
int v[N],ans=-1,n,f[2020][2020];
bool st,flag;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int dfs(int cnt,int l,int r){
    if(r<l) return 0;
    if(f[l][r]) return f[l][r];
    f[l][r]=max(dfs(cnt+1,l+1,r)+cnt*v[l],dfs(cnt+1,l,r-1)+cnt*v[r]);
    return f[l][r];
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)
	v[i]=read();
    for(int i=1;i<=n;i++) f[i][i]=v[i]*n;
    for(int len=2;len<=n;len++)//因为是以len为阶段所以可以转化
	for(int l=1;l<=n-len+1;l++){
	    int r=l+len-1;
	    f[l][r]=max(f[l+1][r]+v[l]*(n-len+1),f[l][r-1]+v[r]*(n-len+1));
	}
    cout<<f[1][n]<<endl;
    return 0;
}

P1220 关路灯

首先看数据范围：\(1≤n≤50\), \(1≤c≤n\) ，再看要求什么：第 \(1\) 盏到第 \(n\) 盏路灯的位置和功率

感觉是区间DP，然后就想状态 \(f[i][j]\) 表示关闭 \(i\)~\(j\) 这段区间所需要的最小花费

“因为在关的过程中适当地调头有可能会更省一些”从这句话可以知道，每一步有两种决策

  1. 折返
  2. 向前

所以我们可以设 \(f[i][j][0/1]\) 第三维表示老张关闭这段区间的灯后，在 \(i\) , \(j\) 哪一端，易得关闭一段区间的灯后在端点处最优

然后就想怎么转移：

由上一题可以知道 \(f[l+1][r] , f[l][r-1]\)​ 是可以更新 \(f[l][r]\)​ ​的，所以得出：

\(f[i][j][0] = min ( f[i+1][j][0] + ( a[i+1] - a[i] ) * ( sum[i] + sum[n] - sum[j] ) , f[i+1][j][1] + ( a[j]-a[i] ) * ( sum[i]+sum[n]-sum[j]) );\)​

\(f[i][j][1] = min ( f[i][j-1][0] + ( a[j] - a[i] ) * ( sum[i-1] + sum[n] - sum[j-1] ) , f[i][j-1][1] + ( a[j]-a[j-1] ) * ( sum[i-1] + sum[n] - sum[j-1] ) );\)

要注意，我们在前往关闭第 \(i\) 盏灯时，这灯是还会有贡献的，\(sum\)数组维护功率前缀和

这是可能会有疑惑：

\(f[i][j]\)​ 为什么就由 \(f[i+1][j]\)​ 转移过来不能由 \(f[i+1][j-1]\)​ 转移来吗？（这句话是我自己的疑惑，记录一下.....

不能，因为每一步只有两种决策

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=60;
bool ed;
int n,c,a[N],sum[N],f[N][N][3],b[N];
bool st,flag;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
signed main(){
    n=read();c=read();
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
    for(int i=1;i<=n;i++){
	sum[i]=sum[i-1]+b[i];
    }
    memset(f,0x3f,sizeof(f));
    f[c][c][1]=f[c][c][0]=0;
    for(int len=2;len<=n;len++)
	for(int i=1;i<=n-len+1;i++){
	    int j=i+len-1;
	    f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*(sum[n]-sum[j]+sum[i]),f[i+1][j][1]+(a[j]-a[i])*(sum[n]-sum[j]+sum[i]));
	    f[i][j][1]=min(f[i][j-1][1]+(a[j]-a[j-1])*(sum[n]-sum[j-1]+sum[i-1]),f[i][j-1][0]+(a[j]-a[i])*(sum[n]-sum[j-1]+sum[i-1]));
	}
    cout<<min(f[1][n][0],f[1][n][1])<<endl;
    return 0;
}

P4302 [SCOI2003]字符串折叠

题目简述：

给你一个字符串，求它折叠后的最短长度

折叠：3(A) = AAA, 2(B) = BB，3(A)C2(B) = AAACBB

解题思路

字符串S，长度保证不超过100，又是字符串的题

想到区间DP

设状态 \(f_i\)\(_j\) 表示 \(i\)~\(j\)的最短长度（好像也只能这么设了

初始化就是 \(dp[i][i]=1\),然后思考如何进行状态转移

一开始想，可以不可以由 \(dp[i+1],dp[j-1]\)​ ,发现是不行的，然后就换一个思路，可以设置断点 \(k\)​​ ，就得到一个显而易见的转移方程：

\(dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\)

直接把两个部分拼起来，但是我们还有一个条件折叠没有用上

通过这个断点 \(k\)​ 我们可以逐一判断，计算循环节 \(len\) 通过 \(check\)​ 函数判断是否可以折叠

得出：

\(dp[i][j]=min(dp[i][j],dp[i][k]+2+m[l/len])\)​

\(m\) 数组存一个数的位数，\(2\)​ 是值括号的长度

为什么一个是 \(dp[i][k]\) 一个是 \(m[l/len]\) ？因为折叠是可以重复折叠的但是判断折叠成什么要看原来的数

记得每一次都要 \(min\) 因为折叠后可能更劣

代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
bool ed;
string s;
int n,m[N],dp[N][N];
bool st,flag;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
bool check(int l,int r,int len){//len表示循环节的长度
    for(int i=l;i<=r;i++){
	if(s[i]!=s[(i-l)%len+l]) return 0;//把l当作1
    }
    return 1;
}
signed main(){
    cin>>s;
    n=s.size();
    s=' '+s;
    for(int i=1;i<=9;i++) m[i]=1;
    for(int i=10;i<=99;i++) m[i]=2;
    m[100]=3;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++) dp[i][i]=1;
    for(int l=2;l<=n;l++)
	for(int i=1,j=i+l-1;j<=n;i++,j++){
	    for(int k=i;k<j;k++){
		int len=k-i+1;
		dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
		if(l%len!=0) continue;
		if(check(i,j,len)) dp[i][j]=min(dp[i][j],dp[i][k]+2+m[l/len]);
	    }
	}
    cout<<dp[1][n]<<endl;
    return 0;
}

P3205 [HNOI2010]合唱队

题目简述

  • 第一个人直接插入空的当前队形中。
  • 对从第二个人开始的每个人，如果他比前面那个人高，那么将他插入当前队形的最右边。如果他比前面那个人矮，那么将他插入当前队形的最左边

给出一个队形，按照给定的排序方法，问有多少种初始排序方案可以得到理想队形

解题思路

我们要求的是构成一个特定的区间有多少种方案，很显然，这是区间DP

那如何设计状态呢？同样的，先设 \(f [i][j]\)​ 表示一段区间的方案，接着我们看进队的方式，也就是决策，

可以发现，一个人进队后要么在左边，要么在右边，所以联想到关路灯这道题，我们可以设 \(f[i][j][0/1]\)​​

表示进队后在左边还是右边，然后就想如何转移，一个人进队后在左边说明，他一定比他前面的人矮，

而他前面可以是 \(i+1,j\) ,将他们进行比较即可，得出：

\(if(a[i]<a[i+1])f[i][j][0]+=f[i+1][j][0]\)

$ if(a[i]<a[j])f[i][j][0]+=f[i+1][j][1]$​

另一边同理（好像统计方案的DP大部分是相加的

代码

#include <bits/stdc++.h>
using namespace std;
const int mod=19650827;
int f[2000][2000][4],n,a[2005];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) f[i][i][0]=1;
    for(int len=2;len<=n;len++)
	for(int i=1,j=i+len-1;j<=n;i++,j++){
	    if(a[i]<a[i+1]) f[i][j][0]+=f[i+1][j][0];
	    if(a[i]<a[j]) f[i][j][0]+=f[i+1][j][1];
	    if(a[j]>a[j-1]) f[i][j][1]+=f[i][j-1][1];
	    if(a[j]>a[i]) f[i][j][1]+=f[i][j-1][0];
	    f[i][j][0]%=mod;
	    f[i][j][1]%=mod;
	}
    cout<<(f[1][n][0]+f[1][n][1])%mod<<endl;
    return 0;
}

CF607B Zuma

题意简述

给定一个串，目标是消灭所有的数字最少的次数，消灭一个数字算一次，如果有回文串，消灭一整串算一次

解题思路

\(1<=n<=500\) 一段一段区间消灭区间DP无疑了

和前面的题一样 \(f [i][j]\) 表示消灭一段区间的最小次数，根据“字符串折叠”这道题的经验，可以直接设出

\(dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])\)

那如何运用回文串这个条件？判断一下头和尾即可，头尾相同则可以继承，设出:

\(if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1]\)

不过这题还有一个恶心之处——初始化，看到上面的 \(i+1,j-1\) 我们就不能从 \(len=2\) 开始枚举了

#include <bits/stdc++.h>
using namespace std;
int f[600][600],a[600],n;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++) f[i][i]=1;
    for(int i=1;i<n;i++) f[i][i+1]=1+(a[i]!=a[i+1]);
    for(int len=3;len<=n;len++)
	for(int i=1,j=i+len-1;j<=n;i++,j++){
	    if(a[i]==a[j]) f[i][j]=f[i+1][j-1];
	    for(int k=i;k<j;k++)
		f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
	}
    cout<<f[1][n]<<endl;
    return 0;
}
上一篇：1. 10min语法速学; 2. 常用命令; 3. Go Modules & goproxy.cn; 4. 进阶; 5. 标准库; 6. 第三方库


下一篇：My Leecode Path_data structure_start from scratch