rnqoj-30- [stupid]愚蠢的矿工-树形DP
把树转化为二叉树,然后再左右DP;#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; struct list { int l; int r; }node[2001]; int val[2001]; int vis[2001][101]; int m,n; int dp(int x,int m) { if(m==0)return 0; if(vis[x][m]!=-1)return vis[x][m]; if(x==0)return 0; int ans=0; ans=dp(node[x].r,m); for(int i=0;i<m;i++) { ans=max(ans,dp(node[x].l,i)+val[x]+dp(node[x].r,m-i-1)); } vis[x][m]=ans; return ans; } void init() { int i; scanf("%d%d",&n,&m); memset(vis,-1,sizeof(vis)); for(i=1;i<=n;i++)scanf("%d",&val[i]); for(i=0;i<=n;i++) { node[i].l=node[i].r=0; } for(i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); node[b].r=node[a].l; node[a].l=b; } cout<<dp(node[0].l,m)<<endl; } int main() { init(); return 0; }
补充:软件开发 , C++ ,