1.dp记录路径
是之前做的一个“通天之潜水”的题有提过关于背包记录路径，当时有两种做法：递归和递推
递归的局限性高一些，或者说实现起来比较困难，递推是开数组模仿dp的过程来记录路径。所以发现递推的方法可以应用到很多dp问题的路径记录上，比如这个最长公共子串的路径记录
#include <bits/stdc++.h>
using namespace std;
const int N = 600+100;
int dp[N][N];
char s1[N];
char s2[N];
string ss[N][N];
int main()
{
cin>>s1+1;
cin>>s2+1;
int len1=strlen(s1+1);
int len2=strlen(s2+1);
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(s1[i]==s2[j])
{
dp[i][j]=dp[i-1][j-1]+1;
ss[i][j]=ss[i-1][j-1]+s1[i];
}
else
{
if(dp[i-1][j]>=dp[i][j-1])
{
dp[i][j]=dp[i-1][j];
ss[i][j]=ss[i-1][j];
}
else
{
dp[i][j]=dp[i][j-1];
ss[i][j]=ss[i][j-1];
}
}
}
}
cout<<dp[len1][len2]<<endl;
cout<<ss[len1][len2]<<endl;
return 0;
}
树形DP
和区间DP和背包问题一样，这类问题属于DP中尚且有一些套路可循的DP
基础的树形DP有：树上背包，普通树形DP
看这题之前我们先来看一个叫分组背包的东西（别看是蓝题，真没选课难）
模板题
#include<bits/stdc++.h>
using namespace std;
int v,n,t;
int x;
int g[205][205];
int i,j,k;
int w[10001],z[10001];
int b[10001];
int dp[10001];
int main()
{
cin>>v>>n;
for(i=1;i<=n;i++)
{
cin>>w[i]>>z[i]>>x;
t=max(t,x);
b[x]++;
g[x][b[x]]=i;
}
for(int i=1;i<=t;i++)
{
for(int j=v;j>=0;j--)
{
for(int k=1;k<=b[i];k++)
{
if(j<w[g[i][k]])
continue;
dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);
}
}
}
cout<<dp[v]<<endl;
return 0;
}
分组背包个人理解：每个物品从一开始的只有一个状态变成了有多个状态，当然，对于一个物品而言多个状态必然是相互冲突的，也就是说只能选择一个状态来做背包
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200000+100
int dp[N];
int a[110][110];
int main()
{
int n,s,m,ans=0;
cin>>s>>n>>m;
for(int i=1;i<=s;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[j][i];
}
}
for(int i=1;i<=n;i++)
{
sort(a[i]+1,a[i]+1+s);
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=s;k++)
{
if(j>a[i][k]*2)
dp[j]=max(dp[j-a[i][k]*2-1]+k*i,dp[j]);
ans=max(ans,dp[j]);
}
}
}
cout<<ans<<endl;
return 0;
}
好的，我们再来看选课这个题
首先，不难看出这是一个树形DP，接着分析会发现各个物品之间有依赖关系，所以这是一个在由依赖性构成的树形关系上做分组背包的问题
1.我们对于这个森林类的依赖关系可以虚拟一个跟节点0，还好这个题是按照拓扑序来的，所以不用建立双向边，不然还需要规定head数组初始为-1（麻烦）
#include <iostream>
using namespace std;
const int N = 300+100;
struct node
{
int nex,to;
};
int n,m;
node edge[N<<1];
int head[N],tot;
int w[N];
int dp[N][N];
void add(int from,int to)
{
edge[++tot].to=to;
edge[tot].nex=head[from];
head[from]=tot;
}
void DFS(int now)
{
dp[now][1]=w[now];
for(int i=head[now];i;i=edge[i].nex)
{
int to=edge[i].to;
DFS(to);
for(int j=m+1;j>0;j--)//背包的容量
{
for(int k=0;k<j;k++)//选择的形态
{
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to][k]);
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a;
cin>>a>>w[i];
add(a,i);
}
DFS(0);
cout<<dp[0][m+1]<<endl;
return 0;
}
接下来是一道十分类似的题目
P2015 二叉苹果树
这题和选课的唯一不同就是在于选课是给的节点权值，这里给的边的权值，那么我们干脆把边想象成节点，节点想象成边，再去建立一个虚拟的根节点即可
#include<bits/stdc++.h>
using namespace std;
const int N =200;
struct node
{
int nex,to,dis;
};
int head[N],tot;
node edge[N<<1];
int dp[N][N],n,m;
void add(int from,int to,int dis)
{
edge[++tot].to=to;
edge[tot].nex=head[from];
edge[tot].dis=dis;
head[from]=tot;
}
void DFS(int now,int fath)
{
for(int i=head[now];i;i=edge[i].nex)
{
if(edge[i].to==fath)
continue;
dp[edge[i].to][1]=edge[i].dis;
DFS(edge[i].to,now);
for(int j=m+1;j>0;j--)
{
for(int k=j-1;k>=0;k--)
{
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[edge[i].to][k]);
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
DFS(1,0);
cout<<dp[1][m+1]<<endl;
return 0;
}
没有上司的舞会
这个就比较轻松了，想明白状态直接做就可以了，注意是从底部节点层层向根节点拓展问题的规模
#include <iostream>
using namespace std;
const int N = 6000+100;
struct node
{
int nex,to;
};
node edge[N<<1];
int rd[N];
int head[N],tot;
int dp[N][2];
void add(int from,int to)
{
edge[++tot].to=to;
edge[tot].nex=head[from];
head[from]=tot;
}
void DFS(int now,int fath)
{
for(int i=head[now];i;i=edge[i].nex)
{
int to=edge[i].to;
if(edge[i].to==fath)
continue;
DFS(edge[i].to,now);
dp[now][0]=max(dp[now][0],max(dp[now][0]+dp[to][1],max(dp[to][0],dp[to][1])));
dp[now][1]=max(dp[now][1],max(dp[now][1]+dp[to][0],dp[to][0]));
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>dp[i][1];
}
for(int i=1;i<=n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
rd[b]++;
}
int root;
for(int i=1;i<=n;i++)
{
if(rd[i]==0)
{
root=i;
break;
}
}
DFS(root,0);
cout<<max(dp[root][0],dp[root][1])<<endl;
return 0;
}
