记录编号	166369	评测结果	AAAAAAAAAA
题目名称	有线电视网	最终得分	100
用户昵称	assassain	是否通过	通过
代码语言	C++	运行时间	0.478 s
提交时间	2015-06-15 09:22:15	内存使用	34.72 MiB

#include<cstdio>
#include<cstring>
#define da(a,b) ((a)>(b)?(a):(b))
using namespace std;
int n,m,a[3002],f[3002][3002],b[3002][2];
struct me
{
	int zuo,you;
}shu[3002];
void zhao(int);
void jian(int);
int in();
void shuru();
int main()
{
   freopen("televi.in","r",stdin);
   freopen("televi.out","w",stdout);
   shuru();
   jian(1);
   zhao(1);
   for(int j=m;j>=1;--j)
	 if(f[1][j]>=0)
       {
			printf("%d\n",j);
			break;
       }
}
void zhao(int x)
{  if(x==0)
	  return;
   zhao(shu[x].you);
   zhao(shu[x].zuo);
  
   for(int i=1;i<=b[x][1];++i)
	 {
	  for(int j=1;j<=i;++j)
	    f[x][i]=da(f[x][i],f[shu[x].zuo][j]+a[x]+f[shu[x].you][i-j]);
	  f[x][i]=da(f[x][i],f[shu[x].you][i]);
	  if(x>n-m)
		f[x][i]=da(f[x][i],f[shu[x].you][i-1]+a[x]);
	 }
}
void jian(int x)
{   if(x==0)
	   return;
	if(x>n-m)
      {
		    jian(shu[x].you);
			b[x][0]=1;
			b[x][1]=b[x][0]+b[shu[x].you][1];
			return;
      }
	jian(shu[x].you);
	jian(shu[x].zuo);
	b[x][0]=b[shu[x].zuo][1];
	b[x][1]=b[x][0]+b[shu[x].you][1];
}
inline void shuru()
{
   memset(f,-0x3f,sizeof(f));
   int k,x,y;
   n=in();
   m=in();
   for(int i=1;i<=n-m;++i)
     {
			k=in();
			if(k)
              {
					x=in();
					y=in();
					a[x]=-y;
					shu[i].zuo=x;
					for(int i=1,p=x;i<=k-1;++i,p=x)
                      {
						x=in();
						y=in();
						a[x]=-y;
						shu[p].you=x;
                      }
              }
			f[i][0]=0;
     }
   for(int j=n-m+1;j<=n;++j)
     {
	   y=in();
	   a[j]+=y;
	   f[j][0]=0;
     }
   f[0][0]=0;
}
inline int in()//优化版  可readin（）负值！
{
	int temp=0;  bool flag=0 ; char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		{
			flag=1;
		}
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar())
	{
		temp=temp*10+c-48;
	}
	if(flag)
	{
		return -temp;
	}
	return temp;
}