树形DP--zoj_3506

??????? http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3506

??????? 题目大意为给定一颗节点带权值的树，和整数k，要求给出一个策略，对这棵树切k刀（对边切，切完保留一部分，丢弃一部分），最后得到的部分的权值和为最大/最小。

??????? f[i][j]为以第i个节点为根，切k刀所得到的最小值。普通dp的想法就是对于某一个节点，如果它为根并保留到最后，那么就在所有的边N中选取k条边，共有C(N,k)种情况，遍历每种情况更新f[i][k].显然这种方法效率是指数级的，会TLE。

??????? 那么如果以节点i为根递归的遍历i的子节点，来更新f[i][0],f[i][1]...f[i][k]，就可以在1个DFS的时间内完成整个DP过程。因此有一下思路，对于节点i的子节点j，考虑3中情况

1）子节点j对应的子树保留，但是子树切1---m刀，节点i对应的树切m-1---0刀。3）子节点j对应的树不保留（也就是说子节点j对应的树至少切1刀）

情况1:f[i][j]=min(f[i][j],f[i][j-m]+f[j][k-m])

情况2:f[i][j]=min(f[i][j],f[i][k-m])(m=1----k)

??????? 注意1：在更新子节点j之前应该先将f[i][m]初始化f[i][m]+=f[j][0];???????

?????? ?注意2：在更新f[i][0]----f[i][k]的过程中一定要逆序更新，因为在更新f[i][j]的时候所用到的子结构f[i][0]---f[i][j-1]应该是上一个子节点更新之后的。如

??????? 注意3：最后的结果也是递归的查找，如果根节点1不再最后的结果中，那么递归的遍历他的子节点，对于子节点j，遍历f[j][p]，其中p的取值应该是max(0,k-除j子树之外的所有边树)---j子树中的所有边数

??????

#include<string> #include<iostream>#include<algorithm>#include<vector>#include<cstdio>#include<string.h>using namespace std;   const int maxn=1005;const int inf=99999999;int fir[maxn],next2[maxn*2],to[maxn*2];int num[maxn];int n,m;int f[maxn][22];int value[maxn];int edgenum;vector<int>v[maxn]; void add_edge(int u,int v){ next2[edgenum]=fir[u]; fir[u]=edgenum; to[edgenum]=v; edgenum++;  }void dfs(int u,int fa){ int size=v[u].size(); for(int i=0;i<size;i++)if(v[u][i]!=fa) {  add_edge(u,v[u][i]);  dfs(v[u][i],u); }}void solve(int u,int p){ num[u]=1; f[u][0]=value[u]; for(int j=1;j<=m;j++)f[u][j]=inf; f[u][0]=0; for(int e=fir[u];e!=-1;e=next2[e])if(to[e]!=p) {  int v=to[e];  solve(v,u);  num[u]+=num[v];  for(int j=m;j>=0;j--)  {   f[u][j]+=f[v][0]; //!!注意1    for(int k=0;k<j;k++)//k!=j 注意2   {    f[u][j]=min(f[u][j],f[u][k]+f[v][j-k]);   }    for(int k=1;k<=j&&k<=num[v];k++)   {    f[u][j]=min(f[u][j],f[u][j-k]);   }   }  } for(int j=0;j<=m;j++)f[u][j]+=value[u]; }int DP(){ int ans=inf; solve(1,-1); ans=min(ans,f[1][m]); if(m>0){  for(int i=2;i<=n;i++)   for(int j=max(m+num[i]-num[1],0);j<num[i]&&j<m;j++)//!注意3    ans=min(ans,f[i][j]); } return ans;} int main(){freopen("e:\\zoj\\zoj_3506.txt","r",stdin); while(scanf("%d%d",&n,&m)==2) {  for(int i=1;i<=n;i++)scanf("%d",&value[i]);  memset(fir,-1,sizeof(fir));  for(int i=1;i<=n;i++)v[i].clear();  edgenum=0;  for(int i=1;i<n;i++)  {   int a,b;   scanf("%d%d",&a,&b);   v[a].push_back(b);   v[b].push_back(a);  }  dfs(1,-1);  for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)f[i][j]=inf;   memset(num,0,sizeof(num));  printf("%d ",DP());  for(int i=1;i<=n;i++)value[i]=-value[i];  for(int i=1;i<=n;i++)   for(int j=0;j<=m;j++)f[i][j]=inf;   memset(num,0,sizeof(num));      printf("%d\n",-DP()); }}

?

?