https://www.luogu.org/PRoblem/show?pid=2014 我一開始想不出來，看了題解后卻發現是最基本的模型 唉~ 這里因為是森林所以我們簡單的把森林合并到一個節點0； f[i][j]表示再i點的子孫里取j個的解； 當然不包括i；
#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){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll;}int dfs(int x){ f[x][0]=v[x]; if(head[x]==-1)return 1; int sum=0,son; for(int k=head[x];k!=-1;k=a[k].next){ son=dfs(a[k].to); sum+=son; for(int j=sum;j;j--) for(int i=0;i<=son;i++) if(j-i-1>=0)//這個-1，1代表a[k].to節點本身 f[x][j]=max(f[x][j],f[x][j-i-1]+f[a[k].to][i]); } return sum+1;//這個+1，加上想節點自己 }int main(){ memset(head,-1,sizeof head); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d",&x,&v[i]); init(x,i); } nn=dfs(0); printf("%d",f[0][m]);}新聞熱點
疑難解答
