这题似乎不用把dp数组初始化成-1
查看原帖
这题似乎不用把dp数组初始化成-1
405894
233L楼主2022/8/14 10:37

看了题解中说初始化成-1是为了排除非法情况

个人认为只要控制好上下界,不打-1也能规避非法情况

提交记录

for(side i:g[id]){
		if(i.v==fa)continue;
		dfs(i.v,id);
		for(int j=min(siz[id]+siz[i.v],m);j>=0;j--)
			for(int k=Max(j-siz[id],0);k<=Min(siz[i.v],j);k++){
				//k=0的情况要最先更新,否则会重复取 
				tot=(ll)k*(m-k)+(ll)(siz[i.v]-k)*(n-m-siz[i.v]+k);
				dp[id][j]=Max(dp[id][j],dp[id][j-k]+dp[i.v][k]+tot*i.w);
			}
		siz[id]+=siz[i.v];
	}
2022/8/14 10:37
加载中...