POJ 2342 树形dp

2019-11-06 07:20:32

字体：大中小

来源：转载

供稿：网友

/*这道题目是说，我们有一颗苹果树，该苹果树除了叶子节点以外的每个节点都分为两枝。每个节点使用 1 到 N 进行编号，其中根节点的编号为 1。每一枝上有若干苹果。为了方便采摘苹果，现在我们要对该苹果进行剪枝，要求剪去指定数目的枝条后，使被剪去的苹果数量最少。我们的任务就是求剪枝后该苹果树上还剩下多少个苹果。输入的第一行包含两个数：N 和 Q (1 ≤ Q ≤ N; 1 < N ≤ 100)。 N 代表苹果树的节点数。Q 代表剪枝后该苹果树上还剩下多少树枝。剩下的 N?1 行用于描述树枝。每行包含三个整数。头两个整数代表节点编号，第三个整数代表该树枝上的苹果的数目。 5 2 1 3 1 1 4 10 2 3 20 3 5 20输出只包含一个数，表示剪枝后该苹果树上还剩下的苹果的数目。注意，剪树时要保留该苹果树的根。（树形dp） 21*/ #include <cstdio> #include <cstdlib> #include <cstring> #define Max(a,b) ((a)>(b) ? (a):(b)) #define N (256) using namespace std; int n,m,ne,x,y,z; int id[N],w[N],v[N],next[N],head[N],lch[N],rch[N],f[N]; int g[N][N]; void add(int x,int y,int z) { id[++ne]= y;w[ne]= z;next[ne] = head[x];head[x] = ne; } void dfs(int x) { for(int p=head[x];p;p=next[p]) if(id[p]!=f[x]) { if(!lch[x]) lch[x]=id[p]; else rch[x]=id[p]; } } int dp(int x,int k) { if(!k) return 0; if(g[x][k]>=0) return g[x][k]; if(!lch[x]) return (g[x][k] = v[x]); for(int i=0;i<k;++i) g[x][k] =Max(g[x][k],dp(lch[x],i) + dp(rch[x],k-i-1)); g[x][k] +=v[x]; return g[x][k]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;++i) { scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z); }dfs(1);memset(g,255,sizeof(g));PRintf("%d/n",dp(1,m+1)); return 0; }

上一篇：实例：sizeof一个指针或者一个数组

下一篇：sdutacm-大家快来A水题

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注