POJ 1155 TELE (树状DP)

题目类型  树状DP
题目意思 给出 n 个点 (2 <= n <= 3000) 和 一个数 m (m 表示 n 个点中有多少个叶子结点) 然后给出每一个非叶子结点与其他点相连的边 这些点和边构成一棵树 非叶子结点与叶子结点之间的边在计算时是加的 而非叶子结点之间的边在计算时是减的 现在问从根 1 可以到达最多多少个叶子结点 (要求根到这些叶子结点的路径权值加起来非负, 相同的边只计算一次)
解题方法 树状DP dp[i][j] -> 表示以 i 结点为根去到 j 个叶子结点的路径权值和加起来最大是多少 那么用子结点 v 去优化父结点 u 的转移方程如下 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k] - W[u][v]); 其中 (1<=j<=子树u拥有的叶子结点数) (1<=k<=子树v拥有的叶子结点数)  即像01背包那样用以子结点为根的子树的一部分去更新父结点 这里要考虑重复使用一部分去更新的情况 详细见代码
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的

#include 
#include 
#include 
#include using namespace std;const int INF = 1<<29;int dp[3010][3010];
int num[3010];
vectorM[3010];
vectorW[3010];
int in[3010], n, m;
int tmp[3010];void DFS(int u, int fa) {if(u > n-m) { // 如果结点 u 是叶子结点的话 直接把与u相连的边的权值赋给 dp[u][1] dp[u][1] = in[u];return ;}for( int i=0; i=j; k-- ) {dp[u][k] = max(dp[u][k], tmp[k-j]+dp[v][j] - W[u][i]); // 如果不使用 tmp数组的话 子结点v的某一比较优的部分会重复使用}	}}
}void Init(int u, int fa) { // 求以 u 为根的子树包含的叶子结点数if(u > n-m) {num[u] = 1;return ;}num[u] = 0;for( int i=0; i=0; i-- ) if(dp[1][i] >= 0) { ans = i; break; }printf("%d\n", ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！