树形$dp$学习笔记
今天学习了树形\(dp\),一开始浏览各大\(blog\),发现都\(TM\)是题,连个入门的\(blog\)都没有,体验极差。所以我立志要写一篇可以让初学树形\(dp\)的童鞋快速入门。
树形\(dp\)
概念类
树形\(dp\)是一种很优美的动态规划,真的很优美真的,前提是在你学会它之后。
实现形式
树形\(dp\)的主要实现形式是\(dfs\),在\(dfs\)中\(dp\),主要的实现形式是\(dp[i][j][0/1]\),\(i\)是以\(i\)为根的子树,\(j\)是表示在以\(i\)为根的子树中选择\(j\)个子节点,\(0\)表示这个节点不选,\(1\)表示选择这个节点。有的时候\(j\)或\(0/1\)这一维可以压掉
基本的\(dp\)方程
选择节点类
\[\begin{cases} dp[i][0]=dp[j][1] \\ dp[i][1]=\max/\min(dp[j][0],dp[j][1])\\ \end{cases} \]树形背包类
\[\begin{cases} dp[v][k]=dp[u][k]+val\\ dp[u][k]=max(dp[u][k],dp[v][k-1])\\ \end{cases} \]例题类
以上就是对树形\(dp\)的基本介绍,因为树形\(dp\)没有基本的形式,然后其也没有固定的做法,一般一种题目有一种做法。
没有上司的舞会
这道题是一树形\(dp\)入门级别的题目,具体方程就用到了上述的选择方程。
#include
#include
#include
#include
#define N 6001
using namespace std;
int ind[N],n,hap[N],dp[N][2],fa[N],root,vis[N],ne[N],po[N];
void work(int x)
{
for(int i = po[x]; i; i = ne[i])
{
work(i);
dp[x][1]=max(max(dp[x][1],dp[x][1]+dp[i][0]),dp[i][0]);
dp[x][0]=max(max(dp[x][0],dp[i][1]+dp[x][0]),max(dp[i][1],dp [i][0]));
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++)
cin >> dp[i][1];
for(int i=1; i<=n; i++)
{
int a,b;
cin >> b >> a;
ind[b]++;
ne[b] = po[a];
po[a] = b;
}
for(int i=1; i<=n; i++)
if(!ind[i])
{
root=i;
break;
}
work(root);
cout << max(dp[root][0],dp[root][1]);
}
最大子树和
这道题的\(dp\)方程有变,因为你的操作是切掉这个点,所以你的子树要么加上价值,要么价值为\(0\),所以\(dp\)方程是
\[dp[u]+=max(dp[v],0) \]#include
#include
#include
#include
#include
using namespace std;
struct edge
{
int next,to;
} e[40000];
int head[40000],tot,rt,maxn;
void add(int x,int y)
{
e[++tot].next=head[x];
head[x]=tot;
e[tot].to=y;
}
int n,dp[20000],ind[20000];
int val[20000],f[20000];
void dfs_f__k(int x,int fa)
{
f[x]=fa;
for(int i=head[x]; i; i=e[i].next)
{
int v=e[i].to;
if(v!=fa)
dfs_f__k(v,x);
}
}
void dfs(int x)
{
dp[x]=val[x];
for(int i=head[x]; i; i=e[i].next)
{
int v=e[i].to;
if(v!=f[x])
{
dfs(v);
dp[x]+=max(0,dp[v]);
}
}
maxn=max(maxn,dp[x]);
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)scanf("%d",&val[i]);
for(int i=1; i<=n-1; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
rt=1;
dfs_f__k(rt,0);
dfs(rt);
printf("%d",maxn);
}
选课
这道题的意思是每本书要想选择一门课,必须要先学会它的必修课,所以这就形成了一种依赖行为,即选择一门课必须要选择必修课。那么他又说要选择的价值最大,这就要用到树形背包的知识了。
树形背包的基本代码形式(即上面的树形背包类)
/*
设dp[i][j]表示选择以i为根的子树中j个节点。
u代表当前根节点,tot代表其选择的节点的总额。
*/
void dfs(int u,int tot)
{
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
for(int k=0;k
然后这就是树形背包的基本形式,基本就是这样做
代码
#include
#include
#include
#include
#include
using namespace std;
int n,m;
struct edge
{
int next,to;
}e[1000];
int rt,head[1000],tot,val[1000],dp[1000][1000];
void add(int x,int y)
{
e[++tot].next=head[x];
head[x]=tot;
e[tot].to=y;
}
void dfs(int u,int t)
{
if (t<=0) return ;
for (int i=head[u]; i; i=e[i].next)
{
int v = e[i].to;
for (int k=0; k
Strategic game
这道题的意思是选择最少的点来覆盖一棵树,可以用最小点覆盖(也就是二分图最大匹配)或者树形\(dp\)来做,因为这里我们的专题是树形\(dp\),所以我们现在就讲树形\(dp\)的做法。
我们做这道题的方法是用选择方程来做,因为你要做最小点覆盖,要么选这个点要么不选对吧。
于是\(dp\)的转移方程就是上述一方程
#include
#include
#include
#include
#include
using namespace std;
int n;
struct edge
{
int next,to;
} e[4000];
int head[4000],tot,dp[4000][2],ind[4000];
void add(int x,int y)
{
e[++tot].next=head[x];
head[x]=tot;
e[tot].to=y;
}
void dfs(int x)
{
dp[x][1]=1;
for(int i=head[x]; i; i=e[i].next)
{
int v=e[i].to;
dfs(v);
dp[x][0]+=dp[v][1];
dp[x][1]+=min(dp[v][0],dp[v][1]);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
memset(head,0,sizeof(head));
memset(ind,0,sizeof(ind));
tot=0;
for(int j=1; j<=n; j++)
{
int a,b;
scanf("%d:(%d)",&a,&b);
for(int i=1; i<=b; i++)
{
int c;
scanf("%d",&c);
ind[c]++;
add(a,c);
}
}
int rt;
for(int i=0; i<=n; i++)
if(!ind[i])
{
rt=i;
break;
}
dfs(rt);
printf("%d\n",min(dp[rt][1],dp[rt][0]));
}
}