【vijos1642】班长的任务

思路：这题就是学习一下算法优化，选择最优方案，O（nm）

可以学习一下《浅谈数据的合理组织》这篇论文

详见代码

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<queue>

 #include<stack>

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define clc(a,b) memset(a,b,sizeof(a))

 #define inf 0x3f3f3f3f

 const int maxn=;

 //countt数组记录每个节点以下所有子节点的数目，s每个节点下代节点数目

 inline int r()

 {

     int x=,f=;char ch=getchar();

     while(ch>''||ch<''){if(ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int a[maxn][maxn],listt[maxn],countt[maxn],s[maxn],v[maxn];

 int f[maxn][maxn];

 int q;

 int tree_traversal(int k)//先序遍历记录根节点

 {

     listt[++q]=k;

     if(s[k]==){return ++countt[k];}

     for(int i=;i<=s[k];i++)countt[k]+=tree_traversal(a[k][i]);

     return ++countt[k];

 }

 int main(){

     int n,m;

     clc(s,);

     clc(listt,);

     clc(a,);

     clc(countt,);

     n=r();

     m=r();

     int t;

     for(int i=;i<=n;i++){

         v[i]=r(),t=r();

         while(t--){

             a[i][++s[i]]=r();

         }

     }

     tree_traversal();

     for(int i=;i<=n;i++){

         f[i][]=;

         f[i][]=v[listt[i]];

     }

     for(int i=n-;i>=;i--){//动态转移方程

         for(int j=;j<=m;j++){

             f[i][j]=max(f[i+][j-]+v[listt[i]],f[i+countt[listt[i]]][j]);

         }

     }

     int ans=-inf;

     for(int i=;i<=m;i++){

         ans=max(ans,f[][i]);

     }

     printf("%d\n",ans);

     return ;

 }