题意:
有棵苹果树,根节点编号为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[......
阅读全文