//针对样例1，列出动态规划过程，能说明上述问题
//for(i=ye[u];i>0;i--)正确 过程如下：
f[1][1]=max(f[1][1],f[1][1]+f[5][0]-3) f[1][1]=max(f[1][1],f[1][0]+f[5][1]-3) 1->5 取一个 最大值 f[2][1]=max(f[2][1],f[2][1]+f[4][0]-3) f[2][1]=max(f[2][1],f[2][0]+f[4][1]-3) 2->4 取一个 最大值 f[2][2]=max(f[2][2],f[2][2]+f[3][0]-2) f[2][2]=max(f[2][2],f[2][1]+f[3][1]-2) f[2][2]=max(f[2][2],f[2][0]+f[3][2]-2) 2->4 2->3 取两个 最大值 f[2][1]=max(f[2][1],f[2][1]+f[3][0]-2) f[2][1]=max(f[2][1],f[2][0]+f[3][1]-2) 2->4 2->3 取一个 最大值 f[1][3]=max(f[1][3],f[1][3]+f[2][0]-2) f[1][3]=max(f[1][3],f[1][2]+f[2][1]-2) f[1][3]=max(f[1][3],f[1][1]+f[2][2]-2) f[1][3]=max(f[1][3],f[1][0]+f[2][3]-2) 1->5 1->4 1->3 取三个 最大值 f[1][2]=max(f[1][2],f[1][2]+f[2][0]-2) f[1][2]=max(f[1][2],f[1][1]+f[2][1]-2) f[1][2]=max(f[1][2],f[1][0]+f[2][2]-2) 1->5 1->4 1->3 取两个 最大值 f[1][1]=max(f[1][1],f[1][1]+f[2][0]-2) f[1][1]=max(f[1][1],f[1][0]+f[2][1]-2) 1->5 1->4 1->3 取一个 最大值 //for(i=1;i<=ye[u];i++)错误 过程如下：
f[1][1]=max(f[1][1],f[1][1]+f[5][0]-3) f[1][1]=max(f[1][1],f[1][0]+f[5][1]-3) 1->5 取一个 最大值 f[2][1]=max(f[2][1],f[2][1]+f[4][0]-3) f[2][1]=max(f[2][1],f[2][0]+f[4][1]-3) 2->4 取一个 最大值 f[2][1]=max(f[2][1],f[2][1]+f[3][0]-2) f[2][1]=max(f[2][1],f[2][0]+f[3][1]-2) 2->4 2->3 取一个 最大值 f[2][2]=max(f[2][2],f[2][2]+f[3][0]-2) f[2][2]=max(f[2][2],f[2][1]+f[3][1]-2) f[2][2]=max(f[2][2],f[2][0]+f[3][2]-2) 2->4 2->3 取两个 最大值 f[1][1]=max(f[1][1],f[1][1]+f[2][0]-2) f[1][1]=max(f[1][1],f[1][0]+f[2][1]-2) 1->5 1->4 1->3 取一个 最大值 f[1][2]=max(f[1][2],f[1][2]+f[2][0]-2) f[1][2]=max(f[1][2],f[1][1]+f[2][1]-2) //此处有问题 f[1][1]可能是1->4 故f[1][2]有可能取成 1->4 1->4 错误从此处开始 f[1][2]=max(f[1][2],f[1][0]+f[2][2]-2) 1->5 1->4 1->3 取两个 最大值 f[1][3]=max(f[1][3],f[1][3]+f[2][0]-2) f[1][3]=max(f[1][3],f[1][2]+f[2][1]-2) f[1][3]=max(f[1][3],f[1][1]+f[2][2]-2) f[1][3]=max(f[1][3],f[1][0]+f[2][3]-2) 1->5 1->4 1->3 取三个 最大值 //分析的过程中，同时将上述的两个顾虑问题解决。
//2017-9-1 17:55 AC #include <stdio.h> #include <string.h> #define INF 999999 int head[3100],cnt=0,ye[3100],f[3100][3100];//f[i][j] i节点及以下共j个用户的最大收益 因收益有正有负，故初始化为绝对值比较大的负数 struct node{//邻接表 int to,next,c; }e[3100];//有向图 void addedge(int u,int v,int c){ cnt++,e[cnt].to=v,e[cnt].c=c,e[cnt].next=head[u],head[u]=cnt; } int max(int a,int b){ return a>b?a:b; } void dfs(int u){ int v,b,i,j,c;//b边 b=head[u]; while(b){ v=e[b].to,c=e[b].c; dfs(v); ye[u]+=ye[v]; for(i=ye[u];i>=1;i--) for(j=0;j<=i;j++) f[u][i]=max(f[u][i],f[u][i-j]+f[v][j]-c);//1 此处写成 f[u][j]=max(f[i][j],f[u][i-j]+f[v][j]-c); b=e[b].next; } } int main(){ int n,m,i,j,p,k,a,c,ans=-INF; memset(head,0,sizeof(head)); memset(ye,0,sizeof(ye)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) f[i][j]=-INF; for(i=1;i<=n;i++) f[i][0]=0;//取0个，值为0 p=n-m; for(i=1;i<=p;i++){ scanf("%d",&k); for(j=1;j<=k;j++){ scanf("%d%d",&a,&c); addedge(i,a,c); } } for(i=p+1;i<=n;i++){ scanf("%d",&c); f[i][1]=c,ye[i]=1; } dfs(1); for(i=ye[1];i>=1;i--){ ans=i; if(f[1][i]>=0)break; } printf("%d\n",ans); return 0; }
