洛谷：P1273 有线电视网（树dp）

题目：

分析：感觉和上一个的选课一样，就是同一根的不同子树之间的关系。需要一个类似背包，但是只能想到这里，后面的想不出来了。

看了题解的dp思路：int B[3005][3005];//表示编号为i的节点所代表的子树在开通j个用户时的最大利润 。

模仿做的第一道树形背包，写下代码，，只有20分，但觉得逻辑没错。：

放弃：树形背包有待突破：

#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > vv;//存放子节点 
vector<vector<int> > vv2;//存放距离 
int A[3005];//支付金钱树。 
int B[3005][3005];//表示编号为i的节点所代表的子树在开通j个用户时的最大利润 
int m,n;
void dfs(int x)
{if(vv[x].size()==0){cin>>A[x];return ;}for(int i=0;i<vv[x].size();i++){dfs(vv[x][i]);}
}
void f(int x)
{if(vv[x].size()==0){B[x][1]=A[x];for(int i=2;i<=n;i++) B[x][i]=-(1<<27);return;}for(int i=0;i<vv[x].size();i++){int c=vv[x][i];f(c);if(i==0) for(int i=1;i<=n;i++) B[x][i]=-(1<<30);for(int k1=n;k1>0;k1--){for(int k2=1;k2<=k1;k2++){B[x][k1]=max(B[x][k1],B[x][k1-k2]+B[c][k2]-vv2[x][i]);//cout<<x<<' '<<k1<<' '<<B[x][k1]<<endl; }}}
}
int main()
{cin>>m>>n;memset(A,-1,sizeof(A)); memset(B,0,sizeof(B));vector<int> v;for(int i=0;i<=m;i++){vv.push_back(v);vv2.push_back(v); }for(int i=1;i<=m-n;i++){int a;cin>>a;for(int j=0;j<a;j++){int a1,a2;cin>>a1>>a2;vv[i].push_back(a1);vv2[i].push_back(a2);}}dfs(1);f(1);for(int i=n;;i--) if(B[1][i]>=0) {cout<<i;//break;return 0;}cout<<endl<<"--------"<<endl;for(int j=1;j<=m;j++){for(int i=0;i<=n;i++) cout<<B[j][i]<<' ';cout<<endl;}
}