https://www.luogu.org/PRoblem/show?pid=1273 其實就是一個背包嘛，每個終端都是一個物品，體積全是1； 網上的題解很多，我copy一段 http://blog.csdn.net/qwsin/article/details/50954669 dp[i][j]表示i節點在其后代中選了j個的最大收入 dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-w) 相信大家都看得懂這個公示，但是也許你會有所疑惑； 這個更新方程需要調用它自己！ 那我怎么可以保證dp[i][j-k]中我沒有包含v這個子節點的情況； 還有為什么j要倒著枚舉？？？？； 其實呢，這個只不過是01背包的樹版； 這相當與一維的01背包； 其實原先應該是dp[i][j][k] 表示第i個節點的前j個字節點中，我在第j個字節點選k個的最大最優情況； 把j這一個壓縮掉就變成了一開始我們說的那個dp方程了； 所以呢，顯然的一開始方程的j要倒著枚舉，原理和一維的01背包是一樣的；
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;struct cs{ int to,next,vv;}a[3001];int head[3001],v[3001],f[3001][3001];int n,m,ll,x,y,z,nn;void init(int x,int y,int z){ ll++; a[ll].to=y; a[ll].vv=z; a[ll].next=head[x]; head[x]=ll;}int dfs(int x){//返回x節點包含了幾個葉子節點 if(!head[x]){ f[x][1]=v[x];return 1; } int sum=0,son=0; for(int k=head[x];k;k=a[k].next){ son=dfs(a[k].to); sum+=son; for(int j=sum;j;j--) for(int i=1;i<=min(son,j);i++) f[x][j]=max(f[x][j],f[x][j-i]+f[a[k].to][i]-a[k].vv); } return sum;}int main(){ memset(f,-63,sizeof f); scanf("%d%d",&n,&m); for(int i=1;i<=n-m;i++){ scanf("%d",&z);nn++; for(int i=1;i<=z;i++){ scanf("%d%d",&x,&y); init(nn,x,y); } } for(int i=1;i<=m;i++)scanf("%d",&v[++nn]); for(int i=0;i<=n;i++)f[i][0]=0; nn=dfs(1); for(int i=m;i>=0;i--) if(f[1][i]>=0){ printf("%d",i);return 0; }}新聞熱點
疑難解答
