算法竞赛DP
《算法竞赛》第 5 章 动态规划
1. DP概念和编程方法
1.1 DP的概念
DP是求解多阶段决策问题最优化的一种算法思想。
解决的问题具有两个特征。
重叠子问题：子问题会重叠，即多个不同问题会用到相同子问题
最优子结构：大问题的最优解由小问题最优解得来，但小问题最优解求解过程与大问题无关。
1.2 DP的两种编程方法
自顶向下（先大问题，再小问题），即递归记忆化搜索。
自底向上（先小问题，再大问题），即递推。
自底向上的优点是编码更直接。
1.3 DP的设计和实现
刷题。
1.4 滚动数组
滚动数组可以减少空间复杂度，但也会损失DP数组存储的信息。
如 01 背包使用滚动数组优化后，无法输出具体方案。
有的DP状态已经是最小空间复杂度，无法再使用滚动数组优化。
两种实现滚动数组的方式。
交替滚动：用 \(dp[0][]\) 和 \(dp[1][]\) 交替滚动
例如01背包
int now=0,old=1;
for(int i=1;i<=n;i++){
swap(now,old);//交替滚动
for(int j=0;j<=c;j++){
if(v[i]>j) dp[now][j]=dp[old][j];
else dp[now][j]=max(dp[old][j],dp[old][j-v[i]]+w[i]);
}
}
自我滚动：自我覆盖
例如01背包
for(int i=1;i<=n;i++){
for(int j=c;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
2. 线性DP
一些经典线性DP问题。
1. 分组背包
有一些物品，分为 n 组，第 i 组第 k 个物品体积为 \(c[i][k]\)，价值为 \(w[i][k]\)。每组最多选一个，给定容量为 C 的背包，如何选使总价值最大。
状态：\(dp[i][j]\)，前 i 组物品装容量 j 的背包获得最大价值。
状态转移方程：\(dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i][k]]+w[i][k])\)
对于 \(dp[i][j]\) 只使用到 \(dp[i-1][]\)，所以可使用滚动数组优化。
即状态转移方程：\(dp[j]=max(dp[j],dp[j-c[i][k]]+w[i][k])\)
for(int i=1;i<=zu;i++)//组数
for(int j=m;j>=0;j--)//体积
for(int k=1;k<=a[i];k++)//第i组物品数
if(j>=v[i][k])
dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
2. 多重背包
给定 n 种物品和一个背包，第 i 种物品的体积为 \(c_i\)，价值为 \(w_i\)，并且有 \(m_i\) 个，背包总容量为 C。使背包总价值最大。
4 种解法。
第一种，转换为01背包，把每种的背包都看作单独物品。
时间复杂度为\(O(C\sum _{i=1}^n m_i)\)。
cin>>n>>C;
for(int i=1;i<=n;i++){
int a,b,c;cin>>a>>b>>c;
while(c--) w.push_back(a),v.push_back(b);
}
for(int i=0;i<w.size();i++){
for(int j=C;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[C]<<"\n";
第二种，转换为分组背包，时间复杂度也为\(O(C\sum _{i=1}^n m_i)\)。
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>m[i];
for(int i=1;i<=n;i++){
for(int j=C;j>=0;j--){
for(int k=1;k<=m[i];k++){
if(k*c[i]>j) break;
dp[j]=max(dp[j],dp[j-k*c[i]]+k*w[i]);
}
}
}
cout<<dp[C];
第三种，二进制拆分优化
若第 i 种物品有 m 个，放进背包的方案有 m+1 种，组合出这 m+1 种并不需要m个物品。根据二进制的原理，任何一个十进制数 X 都可以使用 2 的不同幂次方相加得到，这些幂次方个数只有 \(log_2 X\) 个。所以第 i 种物品的 m 个物品，可以使用 \(log_2 m\) 个表示。复杂度从 \(O(C \sum_{i=1}^n m_i)\) 优化到 \(O(C \sum_{i=1}^n log_2 ~ m_i)\) 。
注意拆分的具体实现，不能全部拆成 2 的倍数，而是先按 2 的幂次方从小到大拆，最后一个小于或等于最大倍数的余数。这样能保证拆出的数相加在 \([1,m_i]\) 范围内，不会大于 \(m_i\) 。
例如，\(m_i=25\)，把它拆成 \(1+2+4+8+10\)，最后余数 10，可保证这拆分数组合不会超过 25。
int n,C,dp[N];
int w[N],c[N],m[N];
int new_n;//二进制拆分后的新物品总数量
int new_w[N],new_c[N],new_m[N];//二进制拆分后的新物品
void solve(){
cin>>n>>C;
for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>m[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m[i];j<<=1){//二进制枚举
m[i]-=j;//减去已拆分的
new_c[++new_n]=j*c[i];//新物品
new_w[new_n]=j*w[i];
}
if(m[i]){
new_c[++new_n]=m[i]*c[i];
new_w[new_n]=m[i]*w[i];
}
}
//下面是滚动数组的 01背包
for(int i=1;i<=new_n;i++)
for(int j=C;j>=new_c[i];j--)
dp[j]=max(dp[j],dp[j-new_c[i]]+new_w[i]);
cout<<dp[C]<<"\n";
}
二进制拆分可以看作多重背包问题的标准解法，下面是最优解法。
第四种，单调队列优化
原理后续DP优化再补。时间复杂度为 \(O(nC)\) ，是最优的解法。
int n,C,dp[N],ans,tmp;
int f[N],que[N],num[N];
void solve(){
cin>>n>>C;
for(int i=1;i<=n;i++){
int v,w,m;
cin>>w>>v>>m;
if(v==0){ans+=m*w;continue;}//体积为0，避免除数为0的情况
int can_use=min(m,C/v);//can_use表示最大可用数量
for(int j=0;j<v;j++){//枚举每一个余数
//注意这要保证转移到所有可以转移点
int all=(C-j)/v,head=1,tail=0;//找到区间内这个余数下有机会转移到的所有点
//每次重置队列
for(int k=0;k<=all;k++){//转移数量从0到all不等
int push_in=f[j+k*v]-k*w;
while(head<=tail&&push_in>=que[tail]) tail--;//维护队列取最大
tail++;
que[tail]=push_in;
num[tail]=k;
while(head<=tail&&num[head]+can_use<k) head++;//无法实现转移的话
f[j+k*v]=max(f[j+k*v],que[head]+k*w);
tmp=max(tmp,f[j+k*v]);
}
}
}
cout<<tmp+ans<<"\n";
}
3. 最长公共子序列（LCS）
给定两个序列 X 和 Y ，找出 X 和 Y 的一个最长公共子序列。
状态：\(dp[i][j]=序列X在第i位置序列Y在第j位置的最长公共子序列\)
状态转移方程： \(dp[i][j]=dp[i-1][j-1]+1,~~X[i]==Y[i];\\ dp[i][j]=max(dp[i-1][j],dp[i][j-1]),~X[i]!=Y[j];\) 时空复杂度都为 \(O(n^2)\)。
P1439这题序列长度为1e5，正常复杂度过不了，但是多了排列的限制条件，就可以将此题转化为LIS。
int a[N],b[N];
void solve(){
int n,len=0;cin>>n;
map<int,int> mp;
for(int i=1;i<=n;i++){
int x;cin>>x;
mp[x]=i;
}
for(int i=1;i<=n;i++){
int x;cin>>x;
a[i]=mp[x];
}
for(int i=1;i<=n;i++){
if(b[len]<=a[i]) b[++len]=a[i];
else{
int x=upper_bound(b+1,b+len+1,a[i])-b;
b[x]=a[i];
}
}
cout<<len<<"\n";
}
基础的LCS
int dp[N][N];
void solve(){
string s1,s2;cin>>s1>>s2;
int n=s1.size(),m=s2.size();
s1=" "+s1,s2=" "+s2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[n][m]<<"\n";
}
4. 最长递增子序列（LIS）
给定一个长度为 n 的数组，找出一个最长的单调递增子序列。
状态：\(dp[i]\) 在以第 \(i\) 个数为结尾的最长上升子序列的最大长度
转移方程：\(dp[i]=max(dp[j]+1),0<j<i,A_j<A_i\)
DP不是LIS问题的最优解，使用树状数组或者贪心二分复杂度更低。
使用DP求解是 \(O(n^2)\) 的，采用树状数组或者贪心+二分是 \(Olog_2n\) 的。
int dp[N],a[N];//DP
void solve(){
int n,ans=0;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++)
if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
ans=max(ans,dp[i]);
}
cout<<ans<<"\n";
}
int a[N],b[N];//贪心+二分
void solve(){
int n,len=0;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
b[++len]=a[1];
for(int i=2;i<=n;i++){
if(a[i]>b[len]) b[++len]=a[i];
else{
int x=lower_bound(b+1,b+len+1,a[i])-b;
b[x]=a[i];
}
}
cout<<len<<"\n";
}
上面这题也是一道LIS的模板。
5. 编辑距离
给定两个单词，计算将第一个单词转换为第二个单词所需的最小操作数。单词允许插入一个字符、删除一个字符、替换一个字符。
状态：\(dp[i][j]\) 表示从 s1 的前 \(i\) 个字符转换到 s2 的前 \(j\) 个字符所需最小操作数。
如果 \(s1[i]==s2[j]\) ，则 \(dp[i][j]=dp[i-1][j-1]\)，因为不需要操作。
如果不等，有三种情况
- 删除 s1 的最后字符（相当于 s1 最后插入），\(dp[i-1][j]+1\)
- 在 s2 插入 s1 的最后字符（相当于 s2 最后删除），\(dp[i][j-1]+1\)
- 将某个单词最后字符替换，\(dp[i-1][j-1]+1\)
即如果 \(s1[i]!=s2[j]\)，则 \(dp[i][j]=min{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]}+1\)
注意初始化，需要将 \(dp[i][0]和dp[0][i]\) 赋值为 \(i\)，因为某串无字符时，需要删加长度字符。
算法复杂度为 \(O(mn)\)。
int dp[N][N];
void solve(){
string s1,s2;cin>>s1>>s2;
int n=s1.size(),m=s2.size();
s1=" "+s1,s2=" "+s2;
for(int i=0;i<=n;i++) dp[i][0]=i;
for(int i=0;i<=m;i++) dp[0][i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1];
else dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
}
}
cout<<dp[n][m];
}
6. 最小划分
给出一个正整数数组，把它分成 \(S_1\) 和 \(S_2\) 两部分，使 \(S_1\) 的数字和与 \(S_2\) 的数字和的差绝对值最小。
转化为求最大容量为 \(sum/2\) 的背包问题。
P3010 Dividing the Gold S - 洛谷
这题不仅需要求最小差，还需要求方案数量。
可以使状态 \(dp[i]\) 为总和为 \(i\) 的方案数。
初始化为 \(dp[0]=1\)，转移方程为 \(dp[i]+=dp[i-a[i]]\)。
但是需要从后往前求出最接近 \(sum/2\) 的值，但是取模可能会破坏。
所以我们使用一个变量存储。
int a[N],ans,dp[N];
void solve(){
int n,sum=0;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];sum+=a[i];
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=sum/2;j>=a[i];j--){
dp[j]+=dp[j-a[i]];
if(dp[j]) ans=max(ans,j);
dp[j]%=mod;
}
}
cout<<sum-ans*2<<"\n"<<dp[ans]%mod;
}
7. 行走问题
给定一个整数 \(n\) ，表示距离的步骤，一个人每次能走 \(1\sim 3\) 步，问走到 \(n\) 的方案数。
状态：\(dp[i]\) 为走到 \(i\) 的方案数 转移方程：\(dp[i]=dp[i-1]+dp[i-2]+dp[i-3],i>2\)，初始化需判断大小
我觉得可以归结于计数类DP。
8. 矩阵最长递增路径
给定一个矩阵，找最长一条路径，要求路径上的数字递增。矩阵的每个点可以向四个方向移动。
第一种方法，记忆化搜索。
第二种方法，DP。
为了满足DP的无后效性，我们需要先从低的点算起，后面高的点对低的没有影响。
从低的点算起可以使用优先队列。
状态：\(dp[i][j]\) 表示以坐标 \((i,j)\) 为终点的最长路径长度
转移方程：\(dp[i][j]=max(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+1,a[i][j]>a[next][next]\)
struct nod{
int i,j,num;
friend bool operator < (nod a,nod b){
return a.num>b.num;
}
};
priority_queue<nod> q;
int bu[4][2]={1,0,0,1,-1,0,0,-1};
int n,m,dp[N][N],a[N][N],ans;
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=1;
cin>>a[i][j];
nod x;x.i=i,x.j=j,x.num=a[i][j];
q.push(x);
}
}
while(!q.empty()){
nod x=q.top();q.pop();
int i=x.i,j=x.j,num=x.num;
for(int k=0;k<4;k++){
int xx=bu[k][0],yy=bu[k][1];
if(a[i+xx][j+yy]<num) dp[i][j]=max(dp[i][j],dp[i+xx][j+yy]+1);
}
ans=max(ans,dp[i][j]);
}
cout<<ans;
}
9. 子集和问题
题意：给定一个非负整数的集合 S，一个值 M，问 S 中是否有一个子集，其子集和为 M。
题解：
暴力的时间复杂度为 \(O(2^n)\)。
状态：\(dp[i][j]=1\) 表示 S 的前 i 个元素存在一个子集和等于 j 。
转移方程：
- 若 \(s[i]>j\)，则不能放入，\(dp[i][j]=dp[i-1][j]\)。
-
若 \(s[i]<=j\)，可以放或者不放，$$dp[i][j]=dp[i-1][j]~ ~dp[i-1][j-s[i]]$$
10. 最优游戏策略
题意：有 n 堆硬币排成一行，价值为 \(v_i\)，n为偶数；两人交替拿硬币，每次只能拿走第一堆或者最后一堆，先手拿的最大价值是多少？
状态：\(dp[i][j]\) 表示从第 i 堆到第 j 堆区间内，先手能拿到的最大值。
在区间 \([i,j]\) ，先手有两个选择：
- 拿 i ，接着对手也可以选择拿 i+1 剩下\([i+2,j]\)，或者拿 j 剩下 \([i+1,j-1]\)
- 拿 j ，接着对手也可以选择拿 i 剩下 \([i+1,j-1]\)，或者拿 j-1 剩下 \([i,j-2]\)。
于是得到状态转移方程：
- 如果 \(i=j\)，\(dp[i][j]=v[i]\)
- 如果 \(i+1=j\)，\(dp[i][j]=max(v[i],v[j])\)
- 否则，后手必然对先手不利的拿法，\(dp[i][j]=max(v[i]+min(dp[i+2][j],dp[i+1][j-1]),v[j]+min(dp[i+1][j-1],dp[i][j-2]))\)
其实也就变化成了区间DP。
11. 矩阵链乘法
题意：给出一个数组 p，其中 \(p[i-1]*p[i]\) 表示矩阵 \(A_i\) 的尺寸，输出最少乘法次数。
还是一个区间DP。
状态：\(dp[i][j]\)，表示区间 \([i,j]\) 的最少乘法次数
转移方程：
- 若 \(i=j\)，\(dp[i][j]=0\)。
- \[dp[i][j]=min(dp[i][k]+dp[k+1][j]+p_{i-1}p_kp_i),i≤k<j\]
12. 布尔括号问题
题意：布尔变量有真假两种取值，3 种逻辑操作与、或、异或。现在输入 n 个取值和 n-1 个逻辑操作，要使结果为真，有多少种括号方案？
状态：
- \(dp[i][j][1]\) 表示子表达式 \([i,j]\) 结果为true的方式数
- \(dp[i][j][0]\) 表示子表达式 \([i,j]\) 结果为false的方式数
#include <bits/stdc++.h>
using namespace std;
bool evaluate(int b1, int b2, char op){
if (op == '&') return b1 & b2;
if (op == '|') return b1 | b2;
return b1 ^ b2;
}
int countWays(string s){
int n = s.length();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
for (int i = 0; i < n; i += 2){
dp[i][i][1] = (s[i] == 'T');
dp[i][i][0] = (s[i] == 'F');
}
for (int len = 2; len < n; len += 2){
for (int i = 0; i < n - len; i += 2){
int j = i + len;
dp[i][j][0] = dp[i][j][1] = 0;
for (int k = i + 1; k < j; k += 2){
char op = s[k];
int leftTrue = dp[i][k - 1][1], leftFalse = dp[i][k - 1][0];
int rightTrue = dp[k + 1][j][1], rightFalse = dp[k + 1][j][0];
if (evaluate(1, 1, op))
dp[i][j][1] += leftTrue * rightTrue;
if (evaluate(1, 0, op))
dp[i][j][1] += leftTrue * rightFalse;
if (evaluate(0, 1, op))
dp[i][j][1] += leftFalse * rightTrue;
if (evaluate(0, 0, op))
dp[i][j][1] += leftFalse * rightFalse;
if (!evaluate(1, 1, op))
dp[i][j][0] += leftTrue * rightTrue;
if (!evaluate(1, 0, op))
dp[i][j][0] += leftTrue * rightFalse;
if (!evaluate(0, 1, op))
dp[i][j][0] += leftFalse * rightTrue;
if (!evaluate(0, 0, op))
dp[i][j][0] += leftFalse * rightFalse;
}
}
}
return dp[0][n - 1][1];
}
int main(){
string s = "T|T&F^T";
cout << countWays(s) << endl;
return 0;
}
13. 最短公共超序列
题意：给定两个字符串，求一个最短的字符串使两个字符串都是它的子序列。
找到两个字符串的LCS，然后将非LCS字符按照原始顺序插入到LCS中。
只求长度的话，\(最短超序列长度=两字符串长度和-LCS长度\)。
3. 数位统计DP
3.1 数位DP的递推实现
3.2 数位DP的记忆化搜索实现
题意：在 \([a,b]\) 中，\(0\sim 9\)出现了多少次。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15;
ll dp[N][N][2][2];//位数,前面几个符合条件,前导0,某位上限
int num[N],now;
ll dfs(int pos,int sum,bool lead,bool limit){
ll ans=0;
if(pos==0) return sum;//递归到0位数，结束返回
if(dp[pos][sum][lead][limit]!=-1) return dp[pos][sum][lead][limit];
int up=(limit?num[pos]:9);
for(int i=0;i<=up;i++){
//计算000~099
if(i==0&&lead) ans+=dfs(pos-1,sum,1,limit&&i==up);
//计算200~299
else if(i==now) ans+=dfs(pos-1,sum+1,0,limit&&i==up);
//计算100~199
else if(i!=now) ans+=dfs(pos-1,sum,0,limit&&i==up);
}
dp[pos][sum][lead][limit]=ans;
return ans;
}
ll solve(ll x){
int len=0;
while(x){
num[++len]=x%10;
x/=10;
}
memset(dp,-1,sizeof(dp));
return dfs(len,0,1,1);
}
int main(){
ll a,b;cin>>a>>b;
for(int i=0;i<=9;i++){
now=i;
cout<<solve(b)-solve(a-1)<<" ";
}
return 0;
}
3.3 数位DP例题
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15;
ll dp[N][N][2][2];//位数,前面几个符合条件,前导0,某位上限
int num[N],now;
ll dfs(int pos,int pre,bool lead,bool limit){
if(pos==0) return 1;
if(dp[pos][pre][lead][limit]!=-1) return dp[pos][pre][lead][limit];
ll ans=0;
int up=limit?num[pos]:9;
for(int i=0;i<=up;i++){
if(abs(i-pre)<2) continue;
if(i==0&&lead) ans+=dfs(pos-1,-2,1,limit&&i==up);
else ans+=dfs(pos-1,i,0,limit&&i==up);
}
dp[pos][pre][lead][limit]=ans;
return ans;
}
ll solve(ll x){
int len=0;//cout<<"x=="<<x<<"\n";
while(x){
num[++len]=x%10;
x/=10;
}
memset(dp,-1,sizeof(dp));
return dfs(len,-2,1,1);
}
int main(){
int T=1;//cin>>T;
while(T--){
ll a,x;cin>>a>>x;
// cout<<solve(a)<<"\n";
cout<<solve(x)-solve(a-1)<<"\n";
}
return 0;
}
ll dp[N][N][N][2][2][2];//位数,上上位，上一位，是否有4，是否有8
int num[N],now;
ll dfs(int pos,int pre1,int pre2,bool n3,bool n4,bool n8,bool limit){
if(n4&&n8) return 0;
if(pos==0) return n3;
if(!limit&&dp[pos][pre1][pre2][n3][n4][n8]!=-1) return dp[pos][pre1][pre2][n3][n4][n8];
ll ans=0;
int up=limit?num[pos]:9;
for(int i=0;i<=up;i++)
ans+=dfs(pos-1,pre2,i,(i==pre1&&i==pre2)||n3,i==4||n4,i==8||n8,limit&&(i==up));
if(!limit) dp[pos][pre1][pre2][n3][n4][n8]=ans;
return ans;
}
ll solve(ll x){
int len=0;
while(x){num[++len]=x%10;x/=10;}
if(len!=11) return 0;
memset(dp,-1,sizeof(dp));
ll ans=0;
for(int i=1;i<=num[len];i++)
ans+=dfs(len-1,-1,i,0,i==4,i==8,i==num[len]);
return ans;
}
4. 状态压缩DP
4.1 Hamilton问题
用 \(dp[S][j]\) 表示集合 S 内的最短Hamilton路径。
转移方程： \(dp[S][j]=min\{dp[S-j][k]+dist(k,j)\},k \in S-j\)
int n,dp[1<<20][21];
int dist[21][21];
int solve(){
memset(dp,0x3f,sizeof(dp));
cin>>n;
for(int i=0;i<n;i++)//邻接矩阵
for(int j=0;j<n;j++)
cin>>dist[i][j];
dp[1][0]=0;
for(int S=1;S<(1<<n);S++)//从小集合扩展到大集合
for(int j=0;j<n;j++)//枚举点j
if((S>>j)&1)//S中含有点j
for(int k=0;k<n;k++)
if((S^(1<<j))>>k&1)//k属于S-j集合中
dp[S][j]=min(dp[S][j],dp[S^(1<<j)][k]+dist[k][j]);
return dp[(1<<n)-1][n-1];
}
4.2 状压DP原理
4.3 状压DP例题
4.4 三进制状压DP
HDU 3001
状态：\(dp[j][i]\) 表示从城市 j 出发，按路径 i 访问 i 中所有城市的最小费用。
转移方程： \(dp[j][i]=min(dp[j][i],dp[k][l]+graph[k][j]) ,k \in (i-j)\) 其中，\(l=i-bit[j]\) ，表示从路径 i 中去掉城市 j。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6e4,inf=0x3f3f3f3f;
int n,m;
int bit[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int tri[N][11];
int dp[11][N];
int graph[11][11];//存图
void init(){//初始化,求所有可能路径
for(int i=0;i<59050;i++){
int t=i;
for(int j=1;j<=10;j++){
tri[i][j]=t%3;
t/=3;
}
}
}
int com_dp(){
int ans=inf;
memset(dp,inf,sizeof(dp));
for(int j=0;j<=n;j++)
dp[j][bit[j]]=0;//初始化，从第j城市出发，只访问j，费用0
for(int i=0;i<bit[n+1];i++){//遍历所有路径，每个i是一条路径
int flag=1;//所有城市都遍历过一次以上
for(int j=1;j<=n;j++){//遍历城市，以j为起点
if(tri[i][j]==0){//是否有一个城市访问次数为0
flag=0;//还没经过所有点
continue;
}
for(int k=1;k<=n;k++){//遍历路径i-j的所有城市
int l=i-bit[j];//从路径i中去掉第j个城市
dp[j][i]=min(dp[j][i],dp[k][l]+graph[k][j]);
}
}
if(flag)//找最小费用
for(int j=1;j<=n;j++)
ans=min(ans,dp[j][i]);//路径i上最下费用
}
return ans;
}
int main(){
init();
while(cin>>n>>m){
memset(graph,inf,sizeof(graph));
while(m--){
int a,b,c;cin>>a>>b>>c;
if(c<graph[a][b]) graph[a][b]=graph[b][a]=c;
}
int ans=com_dp();
if(ans==inf) cout<<"-1\n";
else cout<<ans<<"\n";
}
return 0;
}
5. 区间DP
5.1 石子合并问题
int n,a[N],b[N];
int dp[N][N];
void solve(){
cin>>n;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
cin>>a[i];b[i]=b[i-1]+a[i];
dp[i][i]=0;
}
for(int len=1;len<n;len++)
for(int i=1;i<=n-len;i++){
int j=i+len;
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+b[j]-b[i-1]);
}
}
cout<<dp[1][n]<<"\n";
}
5.2 模板代码
int n,a[N],b[N];
int dp[N][N];
void solve(){
//初始化
for(int len=1;len<n;len++)//区间长度
for(int i=1;i<=n-len;i++){//区间左端点
int j=i+len;//区间右端点
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
}
}
return dp[1][n];
}
5.3 区间DP例题
5.4 二维区间DP
题意：有一个 n*n 的方格图，某些方块为黑色，其余为白色。一次操作可以选定一个 h*w 的矩形，把其中所有方格涂成白色，代价是 \(max(h,w)\)，求最小代价涂所有方格。
时间复杂度 \(O(n^5)\)。
int n;
char a[N][N];
int dp[N][N][N][N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]=='.') dp[i][j][i][j]=0;
else dp[i][j][i][j]=1;//黑格涂成白色需一次
for(int lenx=1;lenx<=n;lenx++)
for(int leny=1;leny<=n;leny++)
for(int x1=1;x1<=n-lenx+1;x1++)
for(int y1=1;y1<=n-leny+1;y1++){
int x2=x1+lenx-1,y2=y1+leny-1;
if(x1==x2&&y1==y2) continue;
dp[x1][y1][x2][y2]=max(abs(x1-x2),abs(y1-y2))+1;//初始值
for(int k=x1;k<x2;k++)
dp[x1][y1][x2][y2]=min(dp[x1][y1][x2][y2],dp[x1][y1][k][y2]+dp[k+1][y1][x2][y2]);
for(int k=y1;k<y2;k++)
dp[x1][y1][x2][y2]=min(dp[x1][y1][x2][y2],dp[x1][y1][x2][k]+dp[x1][k+1][x2][y2]);
}
cout<<dp[1][1][n][n]<<"\n";
}
6. 树形DP
6.1 树形DP基本操作
const int N=1e2+10;
struct nod{
int v=0;
int w=0;
};
vector<nod> edge[N];
int dp[N][N],sum[N];
int n,q;
void dfs(int u,int fa){
for(int i=0;i<edge[u].size();i++){//用i遍历u的所有子节点
int v=edge[u][i].v,w=edge[u][i].w;
if(v==fa) continue;//不回头搜索，避免循环
dfs(v,u);//递归到最深的叶子节点，然后返回
sum[u]+=sum[v]+1;//子树上的总边数
for(int j=min(q,sum[u]);j>=0;j--)
for(int k=0;k<=min(sum[v],j-1);k++)
dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+w);
}
}
void solve(){
cin>>n>>q;
for(int i=1;i<n;i++){
int u,v,w;cin>>u>>v>>w;
edge[u].push_back({v,w});
edge[v].push_back({u,w});
}
dfs(1,0);
cout<<dp[1][q];
}
时间复杂度为 \(O(n)\)。
vector<int> edge[N];
int dp[N][2],a[N],fa[N];
int n,q;
void dfs(int u){
dp[u][0]=0,dp[u][1]=a[u];
for(int i=0;i<edge[u].size();i++){//用i遍历u的所有子节点
int v=edge[u][i];
dfs(v);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][0],dp[v][1]);
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
edge[v].push_back(u);
fa[u]=v;
}
int t=1;
while(fa[t]) t=fa[t];
dfs(t);
cout<<max(dp[t][0],dp[t][1])<<"\n";
}
6.2 背包与树形DP
7. 一般优化
树状数组优化
#define lowbit(x) ((x)&-(x))
const int N=5e3+505;
int a[2*N],dp[2*N][505],t[505][N],n,k;
void update(int x,int y,int d){//更新区间
for(int i=x;i<=k+1;i+=lowbit(i))
for(int j=y;j<=5500;j+=lowbit(j))
t[i][j]=max(t[i][j],d);
}
int query(int x,int y){//查询区间最大值
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
ans=max(ans,t[i][j]);
return ans;
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=k;j>=0;j--){
dp[i][j]=query(j+1,a[i]+j)+1;
update(j+1,a[i]+j,dp[i][j]);
}
cout<<query(k+1,5500);
}
8. 单调队列优化
8.1 单调队列优化原理
8.2 单调队列优化例题
ll n,k,a[N],sum[N],dp[N];
ll ds[N];
int q[N],head=0,tail=1;//递减的单调队列，队头最大
ll que_max(int j){
ds[j]=dp[j-1]-sum[j];
while(head<=tail&&ds[q[tail]]<ds[j]) tail--;//去掉队尾
q[++tail]=j;//进队
while(head<=tail&&q[head]<j-k) head++;
return ds[q[head]];
}
void solve(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++) dp[i]=que_max(i)+sum[i];
cout<<dp[n];
}
