博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj 1304: [CQOI2009]叶子的染色
阅读量:6614 次
发布时间:2019-06-24

本文共 963 字,大约阅读时间需要 3 分钟。

1 #include
2 #include
3 #define N 10009 4 #define inf 100000 5 using namespace std; 6 int b[N],cnt,n,m,c[N],f[N][2],head[N],next[2*N],u[2*N]; 7 void jia(int a1,int a2) 8 { 9 cnt++;10 next[cnt]=head[a1];11 head[a1]=cnt;12 u[cnt]=a2;13 return;14 }15 void dp(int a1)16 {17 b[a1]=1;18 if(a1<=m)19 {20 f[a1][c[a1]]=1;21 f[a1][c[a1]^1]=inf;22 return;23 }24 else25 f[a1][0]=f[a1][1]=1;26 for(int i=head[a1];i;i=next[i])27 if(!b[u[i]])28 {29 dp(u[i]);30 f[a1][0]+=min(f[u[i]][1],f[u[i]][0]-1);31 f[a1][1]+=min(f[u[i]][1]-1,f[u[i]][0]);32 }33 return;34 }35 int main()36 {37 scanf("%d%d",&n,&m);38 for(int i=1;i<=m;i++)39 scanf("%d",&c[i]);40 for(int i=1;i

树形dp 任意可行的节点做根答案都是一样的,f[i][0]表示i节点染白色,1染黑色,所以如果i节点染白色他的子节点中染白色的节点就不用染了。

转载于:https://www.cnblogs.com/xydddd/p/5248918.html

你可能感兴趣的文章
智能时代悄然到来 物联网称王将引爆传感器产业
查看>>
Palo Alto Networks推出云应用框架
查看>>
物理隔离计算机被USB蜜蜂刺破 数据通过无线信号泄露
查看>>
大数据安全分析成未来方向 360市场份额第一
查看>>
利用一点机器学习来加速你的网站
查看>>
安天研究报告:白象的舞步——来自南亚次大陆的网络攻击
查看>>
中国域名现状:应用水平较低,安全仍存隐患
查看>>
Java中HashMap的原理分析
查看>>
React Native入门项目与解析
查看>>
云计算:大势所趋 你准备好了么?
查看>>
看行业观察家和技术专家对大数据在2017年的发展预测
查看>>
可将Windows 10 ISO转为安装U盘的小工具汇总介绍
查看>>
做不好消息推送的摄像头,怎么好意思叫“智能”?
查看>>
OpenStack更新:最小化风险和停机时间
查看>>
物联网如何成了“危”联网
查看>>
国外的农业物联网
查看>>
苹果Alphabet打响密码终结战:手机自动识别身份
查看>>
Intel Atom移动处理器惨败,还被用户和经销商起诉
查看>>
《深入理解Nginx:模块开发与架构解析》一3.10 小结
查看>>
Tego推出TegoOS系统,助力资产管理方案部署
查看>>