正文
Strategic game POJ - 1463 树型dp
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
//题意：就是你需要派最少的士兵来巡查每一条边。相当于求最少点覆盖，用最少的点将所有边都覆盖掉
//题解：
//因为这是一棵树，所以对于每一条边的两个端点，肯定要至少有一个点需要放入士兵，那么对于x->y这一条边
//dp[x][0]=0 表示在x这一点上不放人士兵
//dp[x][1]=1 表示在x这一个点上放入士兵
//那么就有
//dp[x][0]+=dp[y][1];
//dp[x][1]+=min(dp[y][0],dp[y][1]);
//注意这一道题不需要建立一个图，然后再去dfs，因为题目上就是按树从根到叶逐渐给出的。所以可以直接存
//belong用来表示每一个点的层数，pre表示它的父亲节点
第一次我是建了一个图去找dp，然后就MLE了
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=1500;
7 struct edge
8 {
9 int v,next;
10 }e[maxn];
11 int cnt,head[maxn],dp[maxn][5];
12 void add_edge(int x,int y)
13 {
14 e[cnt].v=y;
15 e[cnt].next=head[x];
16 head[x]=cnt++;
17 }
18 int n;
19 void dfs(int x,int pre)
20 {
21 dp[x][0]=0;
22 dp[x][1]=1;
23 for(int i=head[x];i!=-1;i=e[i].next)
24 {
25 int to=e[i].v;
26 //printf("%d %d\n",x,to);
27 if(to==pre)
28 {
29 //printf("**%d**%d\n",x,to);
30 continue;
31 }
32 dfs(to,x);
33 dp[x][0]+=dp[to][1];
34 dp[x][1]+=min(dp[to][1],dp[to][0]);
35 }
36 }
37 int main()
38 {
39 while(~scanf("%d",&n))
40 {
41 memset(head,-1,sizeof(head));
42 cnt=0;
43 memset(dp,0,sizeof(dp));
44 int x,y,sum,u,flag=0;
45 for(int i=1;i<=n;++i)
46 {
47 scanf("%d:(%d)",&x,&sum);
48
49 x++;
50 if(flag==0)
51 {
52 flag=1;
53 u=x;
54 }
55 while(sum--)
56 {
57 scanf("%d",&y);
58 y++;
59 add_edge(x,y);
60 add_edge(y,x);
61 }
62 }
63 //printf("%d**\n",u);
64 dfs(u,u);
65 printf("%d\n",min(dp[u][0],dp[u][1]));
66 }
67 return 0;
68 }
正解：
1 //题意：就是你需要派最少的士兵来巡查每一条边。相当于求最少点覆盖，用最少的点将所有边都覆盖掉
2 //题解：
3 //因为这是一棵树，所以对于每一条边的两个端点，肯定要至少有一个点需要放入士兵，那么对于x->y这一条边
4 //dp[x][0]=0 表示在x这一点上不放人士兵
5 //dp[x][1]=1 表示在x这一个点上放入士兵
6 //那么就有
7 //dp[x][0]+=dp[y][1];
8 //dp[x][1]+=min(dp[y][0],dp[y][1]);
9
10 //注意这一道题不需要建立一个图，然后再去dfs，因为题目上就是按树从根到叶逐渐给出的。所以可以直接存
11 //belong用来表示每一个点的层数，pre表示它的父亲节点
12 #include<stdio.h>
13 #include<string.h>
14 #include<iostream>
15 #include<algorithm>
16 using namespace std;
17 const int maxn=1505;
18 int belong[maxn],pre[maxn],dp[maxn][5],cnt;
19 int n;
20 void DP(int x,int index)
21 {
22 dp[x][0]=0;
23 dp[x][1]=1;
24 for(int i=1;i<=n;++i)
25 {
26 if(pre[i]==x)
27 {
28 DP(i,index+1);
29 dp[x][0]+=dp[i][1];
30 dp[x][1]+=min(dp[i][0],dp[i][1]);
31 }
32 }
33 }
34 int main()
35 {
36 while(~scanf("%d",&n))
37 {
38 memset(pre,0,sizeof(pre));
39 memset(dp,0,sizeof(dp));
40 memset(belong,0,sizeof(belong));
41 cnt=0;
42 int x,y,sum,u,flag=0;
43 for(int i=1;i<=n;++i)
44 {
45 scanf("%d:(%d)",&x,&sum);
46 x++;
47 belong[x]=++cnt;
48 if(flag==0)
49 {
50 flag=1;
51 u=x;
52 }
53 cnt++;
54 while(sum--)
55 {
56 scanf("%d",&y);
57 y++;
58 pre[y]=x;
59 // add_edge(x,y);
60 // add_edge(y,x);
61 belong[y]=cnt;
62 }
63 }
64 pre[u]=-1;
65 DP(u,1);
66 printf("%d\n",min(dp[u][0],dp[u][1]));
67 }
68 return 0;
69 }
