bzoj4033:[HAOI2015]树上染色

传送门

我一开始想的是考虑每个点的颜色
设的状态就是\(f[i][j]\)表示\(i\)子树里有\(j\)个黑点的\(i\)子树的收益最大值，后来发现无法转移
那么考虑答案的统计，可以对于边统计答案
那么我们就可以考虑\(f[i][j]\)为\(i\)子树里有\(j\)个黑点对于全局答案的贡献最大值
也就是对于边考虑统计答案，假设边的长度是\(val\)
那么转移方程就是：
\(f[x][i]=max\{f[x][i],f[son][j]+f[x][i-j]+val*j*(k-j)+val*(size[son]-j)*(n-size[son]-k+j)\}\)
我代码挺慢的，卡过去的！
代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; void read(int &x) {char ch;bool ok;for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar());if(ok) x=-x; } #define rg register const int maxn=2e3+10; int n,m,pre[maxn*2],nxt[maxn*2],h[maxn],v[maxn*2],cnt,size[maxn]; long long f[maxn][maxn]; void add(int x,int y,int z) {pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt,v[cnt]=z;pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt,v[cnt]=z; } void dfs(int x,int fa) {size[x]=1;f[x][0]=f[x][1]=0;for(rg int i=h[x];i;i=nxt[i])if(pre[i]!=fa){dfs(pre[i],x);size[x]+=size[pre[i]];}for(rg int i=h[x];i;i=nxt[i])if(pre[i]!=fa)for(rg int j=min(m,size[x]);j>=0;j--)for(rg int k=0;k<=min(j,size[pre[i]]);k++)if(~f[x][j-k])f[x][j]=max(f[x][j],f[pre[i]][k]+f[x][j-k]+1ll*k*(m-k)*v[i]+1ll*(size[pre[i]]-k)*(n-size[pre[i]]-m+k)*v[i]); } signed main() {read(n),read(m);memset(f,-1,sizeof f);for(rg int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),add(x,y,z);dfs(1,0),printf("%lld\n",f[1][m]); }

转载于:https://www.cnblogs.com/lcxer/p/10495178.html

总结

以上是生活随笔为你收集整理的bzoj4033:[HAOI2015]树上染色的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。