背景

十八居士的毕业典礼（1）

描述

福州时代中学2009届十班同学毕业了，于是班长PRT开始筹办毕业晚会，但是由于条件有限，可能每个同学不能都去，但每个人都有一个权值，PRT希望来的同学们的权值总和最大。

十班有一个周密的电话通知网络，它其实就是一棵树，根结点为班长PRT，由她来负责通知她的下线（也就是儿子节点），下线们继续通知自己的下线（不一定每个下线都要通知），任何人都可以不去：”
为了使权值总和最大，班长想安排一下人，但是人数很多，人脑是难以应付的，所以她找到十八居士，让他编程用电脑解决。

格式

输入格式

输入第一行两个整数n，m表示有n位同学，至多只能去m位同学。(1<=m<=n)
接下来2*n行，每两行代表一个同学的信息（如果这位同学没有子节点，就只有一行）。

每个同学的第一行两个整数p，s，表示这位同学权值为p，子节点个数s；(-100<=p<=100)
第二行s个整数，表示这位同学的子节点的编号。

班长的编号一定为1。

对于20%数据1<=n<=10
对于60%数据1<=n<=100
对于100%数据1<=n<=1000

输出格式

输出一个整数，表示权值的最大值。

样例

样例输入1

样例输出1

`My Solution`

id序列树形dp!!!

神秘!

const int maxn=;

int d[maxn];               -------->WA!!!!

int d[];                -------->AC!!!!

于是我改成了

const int maxn=;

int d[maxn];

AC!!!

C++基本的东西还要多学

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<vector>

 using namespace std;

 #define inf 0x3f3f3f3f

 inline int read(){

     int re=;

     char ch;

     bool flag=;

     while((ch=getchar())!='-'&&(ch<''||ch>''));

     ch=='-'?flag=:re=ch-'';

     while((ch=getchar())>=''&&ch<='')  re=(re<<)+(re<<)+ch-'';

     return flag?-re:re;

 }

 struct edge{

     int to,next;

     edge(int to=,int next=):

         to(to),next(next){}

 };

 const int maxn=;

 vector<edge> edges;

 int n,m;

 int head[maxn];

 int w[maxn],num[maxn];

 int dp[maxn][maxn];

 int id[maxn],count[maxn],q=;

 int root=;

 int cnt=;

 int ans=-inf;

 inline void add_edge(int from,int to){

     edges.push_back(edge(to,head[from]));

     head[from]=++cnt;

 }

 void init(){

     n=read();  m=read();

     edges.push_back(edge(,));

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

         w[i]=read();

         num[i]=read();

         for(int j=;j<=num[i];j++){

             int to=read();

             add_edge(i,to);

         }

     }

 }

 void dfs(int x){

     id[++q]=x;

     count[x]=;

     for(int ee=head[x];ee;ee=edges[ee].next){

         dfs(edges[ee].to);

         count[x]+=count[edges[ee].to];

     }

 }

 void solve(){

     memset(dp,-,sizeof dp);

     dfs(root);

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

         dp[i][]=;

         dp[i][]=w[id[i]];

     }

     for(int i=n-;i>;i--)

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

             dp[i][j]=max(dp[i+][j-]+w[id[i]],dp[i+count[id[i]]][j]);

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

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

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

 }

 int main(){

     //freopen("temp.in","r",stdin);

     init();

     solve();

     return ;

 }

于是他走了就像他没有来过一样

班长

[vijos 1642]班长的任务 [树形dp]

背景

描述

格式

输出格式

样例

My Solution

`My Solution`