<更新提示>
<第一次更新> 通过两道简单的例题,我们来重新认识树形DP。
<正文>
战略游戏(luoguP1026)
Description
Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。
请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵。
Input Format
输入文件中数据表示一棵树,描述如下: 第一行 N,表示树中结点的数目。 第二行至第N+1行,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连),接下来k个数,分别是每条边的另一个结点标号r1,r2,...,rk。 对于一个n(0<n<=1500)个结点的树,结点标号在0到n-1之间,在输入文件中每条边只出现一次。
Output Format
输出文件仅包含一个数,为所求的最少的士兵数目。
Sample Input
4
0 1 1
1 2 2 3
2 0
3 0
Sample Output
1
解析
在树形图求解最优化问题,很明显就是一道树形DP的模板题。
我们根据树形\(DP\)通常设置状态的套路来设计这道题的状态:\(f[i][0/1]\)代表以\(i\)为根的子树中的最小士兵数,\(1\)代表节点i放了士兵,\(0\)代表节点i没放士兵。
对于状态的转移,我们可以分两种情况讨论:
那么所对应的状态转移方程就是:
\\2.f[i][0]=\sum_{j \in son(i)}f[j][1]
\]
注意到题中没有明确的树根的指明,所以我们只要随便找一个入度为0的点当做树根执行记忆化搜索即可。
\(Code:\)
#include<bits/stdc++.h>
using namespace std;
const int N=1500+30;
int n,f[N][2],ans=0x3f3f3f3f,vis[N];vector < int >Link[N];
inline void input(void)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int index,num,temp;
scanf("%d%d",&index,&num);
for(int j=1;j<=num;j++)
{
scanf("%d",&temp);
Link[index].push_back(temp);
vis[temp]=1;
}
}
}
inline void dp(int root)
{
f[root][1]=1;
f[root][0]=0;
for(int i=0;i<Link[root].size();i++)
{
int Son=Link[root][i];
dp(Son);
f[root][0]+=f[Son][1];
f[root][1]+=min(f[Son][0],f[Son][1]);
}
return;
}
int main(void)
{
freopen("strategi.in","r",stdin);
freopen("strategi.out","w",stdout);
input();
int root;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
root=i;
break;
}
}
dp(root);
printf("%d\n",min(f[root][0],f[root][1]));
}
最大利润(SMOJ1782)
Description
政府邀请了你在火车站开饭店,但不允许同时在两个相连接的火车站开。
任意两个火车站有且只有一条路径,每个火车站最多有50个和它相连接的火车站。
告诉你每个火车站的利润,问你可以获得的最大利润为多少。
Input Format
第一行输入整数N(<=100000),表示有N个火车站,分别用1,2,...,N来编号。
接下来N行,每行一个整数表示每个站点的利润,接下来N-1行描述火车站网络,每行两个整数,表示相连接的两个站点。
Output Format
输出一个整数表示可以获得的最大利润
Sample Input
6
10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4
Sample Output
90
解析
这道题和上一道题很像,都是很明显的树形\(DP\)。但是两道题有不同之处:上一题是覆盖相邻的边,但这题是覆盖相邻的点。上一题是必须全部覆盖,这一题是可以不全部覆盖,但不能重叠。我们仍然可以设\(f[i][0/1]\)代表以\(i\)为根的子树中的最大利润,\(0\)代表节点i没有开餐馆,\(1\)代表节点\(i\)开了餐馆。
状态的转移就和上一题很相似了:
状态转移方程:
\\f[i][0]=\sum_{j \in son(i)}f[j][0]+a[i]
\]
注意在记忆化搜索的时候需要开一个访问数组标记,避免递归死循环。
\(Code:\)
#include<bits/stdc++.h>
using namespace std;
const int N=100000+80;
int n,f[N][2],a[N],vis[N],ans=0;
vector < int > Link[N];
inline void input(void)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
Link[u].push_back(v);
Link[v].push_back(u);
}
}
inline void dp(int root)
{
f[root][0]=0;
f[root][1]=a[root];
for(int i=0;i<Link[root].size();i++)
{
int Son=Link[root][i];
if(vis[Son])continue;
vis[Son]=1;
dp(Son);
f[root][0]+=max(f[Son][1],f[Son][0]);
f[root][1]+=f[Son][0];
}
return;
}
int main(void)
{
freopen("profit.in","r",stdin);
freopen("profit.out","w",stdout);
input();
memset(f,0x00,sizeof f);
memset(vis,0x00,sizeof vis);
vis[1]=1;
dp(1);
printf("%d\n",max(f[1][1],f[1][0]));
}
<后记>