题意:
有棵苹果树,根节点编号为1.边权为该边上苹果数. 问保留x条树枝时, 能够保留的最多苹果数.
思路:
树DP.
令dp[ i ][ j ] 表示以 i 为根的子树保留 j 条树枝(包括 i 与其父节点相连的那一条在内)最多有多少苹果.
枚举关于子树的不同分配方案, 选择最大的.
树DP的特殊之处就在于它的第一维的变化是沿着dfs的方向走的.
#include <cstdio> #include <cstring> const int MAXN = 111; int n, m, f[MAXN][MAXN], data[MAXN][MAXN]; bool vis[MAXN]; struct Tree { int l, r, v; inline Tree() { l = r = v = 0; } }a[MAXN];///a是森林... inline void build(const int &x)///递归也可以inline啊...这样就不会爆栈了么? {///const的引用,所以也可以传一个常量进去.为了省内存? vis[x] = true; for (int i = 1; i <= n; i++) if (!vis[i] && data[x][i]) { if (!a[x].l) a[x].l = i; else//说了是二叉 a[x].r = i; a[i].v = data[x][i];///将边权下落到远端点权 build(i); } } inline int dfs(const int &x, const int &left) { if (!x || !left)//没有名额了或者没有儿子了 return 0; if (f[x][left])///记忆化搜索 return f[x][left];///往下细分会有重叠 int maxn = 0; for (int i = 0; i < left; i++)///实际保留的条数要小1 { int l = dfs(a[x].l, i), r = dfs(a[x].r, left - i - 1); if (maxn < l + r) maxn = l + r; }///返回的时候,加上了自己.其实一共也就是这一条语句执行了"加"的操作.这是合理的. f[x][left] = maxn + a[x].v;///记忆化搜索 return f[x][left]; } int main() { while (scanf("%d%d", &n, &m) != EOF) { memset(data, 0, sizeof(data)); memset(vis, false, sizeof(vis)); memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) a[i] = Tree();///分配给a一个个元素(这句多余不?) for (int i = 1; i < n; i++) { int tmp1, tmp2, tmpv; scanf("%d%d%d", &tmp1, &tmp2, &tmpv); data[tmp1][tmp2] = data[tmp2][tmp1] = tmpv;///邻接矩阵 } build(1); int ans = dfs(1, m + 1); ///留下m条树枝,但是有一条是连着自己这个节点的 ///这是在dfs的过程中一直遵循的,否则无法分呐. ///只能讲通向儿子节点的边划到儿子树中,否则统计的时候就会混乱 printf("%d\n", ans); } return 0; }
自己敲一遍:
#include <cstdio> #include <vector> using namespace std; const int MAXN = 105; int dp[MAXN][MAXN],n,m; typedef struct node { int v,w; node(){} node(int _v, int _w):v(_v),w(_w){} }node; typedef struct tree { int l,r,w; tree(){} }tree; vector<node> edge[MAXN]; tree a[MAXN]; bool vis[MAXN]; inline void build(const int& x) { vis[x] = true; for(int i=0;i<edge[x].size();i++) { int y = edge[x][i].v; if(!vis[y]) { if(!a[x].l) a[x].l = y; else a[x].r = y; a[y].w = edge[x][i].w; build(y); } } } inline int dfs(const int& i, const int& j) { if(!i || !j) return 0; if(dp[i][j]) return dp[i][j]; int max = 0; for(int k=0;k<j;k++) { int l = dfs(a[i].l, k), r = dfs(a[i].r, j-1-k); if(max<l+r) max = l+r; } dp[i][j] = max + a[i].w; return dp[i][j]; } int main() { scanf("%d %d",&n,&m); for(int i=1,u,v,w;i<n;i++) { scanf("%d %d %d",&u,&v,&w); edge[u].push_back(node(v,w)); edge[v].push_back(node(u,w)); } build(1); int ans = dfs(1, m+1); printf("%d\n",ans); }