【BZOJ 3090】树形DP

3090: Coci2009 [podjela]

Description

有 N 个农民, 他们住在 N 个不同的村子里. 这 N 个村子形成一棵树.
每个农民初始时获得 X 的钱.
每一次操作, 一个农民可以从它自己的钱中, 取出任意数量的钱, 交给某个相邻村子的农民.

对于每个农民给定一个值 v_i, 求
    (1) 最少需要多少次操作, 使得每个农民最终拿到的钱 >= 给定的值.

Input

    第1行: 一个整数 N (1 <= N <= 2000)
    第2行: 一个整数 X (0 <= X <= 10000)
    第3行: N 个整数, 表示 v_i. 保证所有 v_i 的和 <= N * X
    第4..N+2行: 每行两个 1..N 的数, 表示树上的一条边. 边是双向的.

Output

    第1行: 一个整数, 最少需要的操作次数

Sample Input

6
15
10 20 18 16 6 16
1 4
4 5
4 6
6 2
5 3

Sample Output

5

HINT

Source

【分析】

　　之前做过很多次这种移来移去的题目了。

　　如果有环的，我就做过BZOJ 1045 一道数学题。

　　如果没环，目标值的和等于初始值的和，那么挺唯一的，直接for就好了。

　　这题就是目标值的和小于等于初始值的和的，考虑DP。

　　一开始的想法当然是f[x][y]表示x这个子树，然后y这个点的值，然后什么最小代价。

　　但是爆空间超时啊，不如把f中的y和答案换一下位置，因为显然操作次数少于子树大小，

　　f[x][y]表示x这棵子树在操作y次之后满足目标值，最少要x从父亲那里拿多少东西（若f的值小于0则表示不仅不用从父亲那里拿东西，还可以给-f[x][y]的东西给父亲）

　　然后DP。

　　这种要满足每个子树的题我真的是不太擅长，于是我最好的解决方案就是滚动一下了。

　　还有要注意的是x<=n,y<=x，所以看似三重循环，实际是n^2的，这个是之前做树形依赖的题知道的，因为可以看成只会在LCA的时候for到那两个东西。

　　大神的方法跟我的差不多然后讲的比我清楚：http://blog.csdn.net/visit_world/article/details/54297322

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define Maxn 2010
 8 #define INF 0xfffffff
 9 
10 int mymin(int x,int y) {return x<y?x:y;}
11 int mymax(int x,int y) {return x>y?x:y;}
12 
13 int w[Maxn],ww;
14 
15 struct node
16 {
17     int x,y,next;
18 }t[Maxn*2];
19 int first[Maxn],len;
20 
21 void ins(int x,int y)
22 {
23     t[++len].x=x;t[len].y=y;
24     t[len].next=first[x];first[x]=len;
25 }
26 
27 int f[Maxn][Maxn],g[2][Maxn],sm[Maxn];
28 
29 void dfs(int x,int ff)
30 {
31     sm[x]=1;
32     for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff)
33     {
34         int y=t[i].y;
35         dfs(y,x);
36         sm[x]+=sm[y];
37     }
38     if(sm[x]!=1)
39     {
40         int p=0;
41         for(int j=0;j<=sm[x];j++) g[0][j]=0;
42         for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff)
43         {
44             int y=t[i].y;
45             for(int j=0;j<=sm[x];j++) g[1-p][j]=INF;
46             //j-k<=sm[x]-1-sm[y]
47             //k>=j-sm[x]+sm[y]+1
48             for(int j=0;j<=sm[x];j++)
49             {
50                 int st=mymax(j-sm[x]+sm[y]+1,0);
51                 for(int k=st;k<=sm[y];k++)
52                 {
53                     if(k>j) break;//j-k>=0
54                     if(f[y][k]>0)
55                     {
56                         if(k>=1) g[1-p][j]=mymin(g[1-p][j],g[p][j-k]+f[y][k-1]);
57                     }
58                     else
59                     {
60                         if(k>=1) g[1-p][j]=mymin(g[1-p][j],g[p][j-k]+f[y][k-1]);//give father
61                         if(k!=sm[y]) g[1-p][j]=mymin(g[1-p][j],g[p][j-k]);
62                     }
63                 }
64             }
65             p=1-p;
66         }
67         for(int j=0;j<sm[x];j++) f[x][j]=g[p][j];
68     }
69     for(int j=0;j<sm[x];j++)
70     {
71         f[x][j]=f[x][j]+w[x]-ww;
72         // printf("f[%d][%d]=%d
",x,j,f[x][j]);
73     }
74 }
75 
76 int main()
77 {
78     int n;
79     scanf("%d%d",&n,&ww);
80     len=0;
81     memset(first,0,sizeof(first));
82     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
83     for(int i=1;i<n;i++)
84     {
85         int x,y;
86         scanf("%d%d",&x,&y);
87         ins(x,y);ins(y,x);
88     }
89     memset(f,0,sizeof(f));
90     dfs(1,0);
91     for(int i=0;i<sm[1];i++) if(f[1][i]<=0) {printf("%d
",i);break;}
92     return 0;
93 }

View Code

2017-03-22 10:26:09

【BZOJ 3090】 树形DP

3090: Coci2009 [podjela]

Description

Input

Output

Sample Input

Sample Output

HINT

Source

【BZOJ 3090】树形DP