POJ1155 TELE（树形DP）

题目是说给一棵树，叶子结点有负权，边有正权，问最多能选多少个叶子结点，使从叶子到根的权值和小于等于0。

考虑数据规模表示出状态：dp[u][k]表示在u结点为根的子树中选择k个叶子结点的最小权值

最后就从d[1][k]中找满足的最大的k。不过单这样转移时间复杂度是指数级，显然这题就是用树上背包了。

不过其实这题时间复杂度不会算= =反正感觉挺靠谱，交了就AC了。。

又做了一道树上背包，HDU1561和POJ3345。

1 #include

2 #include

3 #include

4 using namespace std;

5 #define INF (1<<29)

6 #define MAXN 3001

7 struct Edge{

8 int u,v,w,next;

9 }edge[MAXN];

10 int NE,head[MAXN];

11 void addEdge(int u,int v,int w){

12 edge[NE].u=u; edge[NE].v=v; edge[NE].w=w;

13 edge[NE].next=head[u]; head[u]=NE++;

14 }

15

16 int d[MAXN][MAXN],size[MAXN];

17 void dfs(int u){

18 bool isleaf=1;

19 for(int i=head[u]; i!=-1; i=edge[i].next){

20 int v=edge[i].v;

21 dfs(v);

22 size[u]+=size[v];

23 isleaf=0;

24 }

25 if(isleaf) size[u]=1;

26 }

27 int val[MAXN];

28 void dp(int u){

29 bool isleaf=1;

30 for(int i=head[u]; i!=-1; i=edge[i].next){

31 int v=edge[i].v;

32 dp(v);

33 isleaf=0;

34 for(int j=size[u]; j>=1; --j){

35 for(int k=1; k<=min(j,size[v]); ++k) d[u][j]=min(d[u][j],d[u][j-k]+d[v][k]+edge[i].w);

36 }

37 }

38 if(isleaf) d[u][1]=-val[u];

39 }

40 int main(){

41 memset(head,-1,sizeof(head));

42 int n,m,k,a,b;

43 scanf("%d%d",&n,&m);

44 for(int i=1; i<=n; ++i){

45 for(int j=1; j<=m; ++j) d[i][j]=INF;

46 }

47 for(int i=1; i<=n-m; ++i){

48 scanf("%d",&k);

49 while(k--){

50 scanf("%d%d",&a,&b);

51 addEdge(i,a,b);

52 }

53 }

54 for(int i=n-m+1; i<=n; ++i){

55 scanf("%d",val+i);

56 }

57 dfs(1);

58 dp(1);

59 for(int i=m; i>=0; --i){

60 if(d[1][i]<=0){

61 printf("%d",i);

62 break;

63 }

64 }

65 return 0;

66 }

参考链接