思路：这题就是学习一下算法优化，选择最优方案，O（nm）
可以学习一下《浅谈数据的合理组织》这篇论文
详见代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define LL long long 9 #define clc(a,b) memset(a,b,sizeof(a))10 #define inf 0x3f3f3f3f11 const int maxn=1010;12 //countt数组记录每个节点以下所有子节点的数目，s每个节点下代节点数目 13 inline int r()14 {15 int x=0,f=1;char ch=getchar();16 while(ch>'9'||ch<'0'){ if(ch=='-') f=-1;ch=getchar();}17 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}18 return x*f;19 }20 int a[maxn][maxn],listt[maxn],countt[maxn],s[maxn],v[maxn];21 int f[maxn][maxn];22 int q;23 int tree_traversal(int k)//先序遍历记录根节点24 {25 listt[++q]=k;26 if(s[k]==0){ return ++countt[k];}27 for(int i=1;i<=s[k];i++)countt[k]+=tree_traversal(a[k][i]);28 return ++countt[k];29 }30 int main(){31 int n,m;32 clc(s,0);33 clc(listt,0);34 clc(a,0);35 clc(countt,0);36 n=r();37 m=r();38 int t;39 for(int i=1;i<=n;i++){40 v[i]=r(),t=r();41 while(t--){42 a[i][++s[i]]=r();43 }44 }45 tree_traversal(1);46 for(int i=1;i<=n;i++){47 f[i][0]=0;48 f[i][1]=v[listt[i]];49 }50 for(int i=n-1;i>=1;i--){ //动态转移方程51 for(int j=1;j<=m;j++){52 f[i][j]=max(f[i+1][j-1]+v[listt[i]],f[i+countt[listt[i]]][j]);53 }54 }55 int ans=-inf;56 for(int i=1;i<=m;i++){57 ans=max(ans,f[1][i]);58 }59 printf("%d\n",ans);60 return 0;61 }