【bzoj4007】[JLOI2015]战争调度 暴力+树形背包dp
题目描述
给你一棵 $n$ 层的完全二叉树,每个节点可以染黑白两种颜色。对于每个叶子节点及其某个祖先节点,如果它们均为黑色则有一个贡献值,如果均为白色则有另一个贡献值。要求黑色的叶子节点数目不超过 $m$ ,求最大总贡献值。
$n\le 10$
输入
第一行两个数 n;m。接下来 2^(n-1) 行,每行n-1 个数,第 i 行表示编号为 2^(n-1)-1+ i 的平民对其n-1直系上司的作战贡献度,其中第一个数表示对第一级直系上司,即编号为 (2^(n-1)-1+ i)/2 的贵族的作战贡献度 wij,依次往上。接下来 2^(n-1)行,每行n-1个数,第i行表示编号为 2^(n-1)-1+ i的平民对其n-1个直系上司的后勤贡献度,其中第一个数表示对第一级直系上司,即编号为 (2^(n-1)-1+ i)/2 的贵族的后勤贡献度 fij ,依次往上。
输出
一行一个数表示满足条件的最大贡献值
样例输入
3 4
503 1082
1271 369
303 1135
749 1289
100 54
837 826
947 699
216 389
样例输出
6701
题解
暴力+树形背包dp
[NOI2006]网络收费 的套路。
提前计算叶子节点的总贡献,设 $f[i][j]$ 表示以 $i$ 为根的子树中,$j$ 个叶子节点的颜色为黑色( $j$ 个平民选择战争)的最大总贡献值。
那么这显然是一个树形背包问题,处理左右节点后背包合并即可。
但是由于叶子节点的贡献与其祖先节点的颜色选择有关,我们不能直接得到贡献。由于这是一棵完全二叉树,因此可以暴力枚举每个非叶子节点的颜色。
这样有递归式 $T(1)=O(\log k),T(k)=4T(\frac k2)+O(k^2)$ ,不考虑 $T(1)$ 时根据主定理解得 $T(k)=O(k^2\log k)$ ,考虑 $T(1)$ 时 $T(1)$ 被计算了 $k^2$ 次,贡献为 $O(k^2\log k)$ 。
因此总的时间复杂度是正确的,为 $O(2^{2n}·n)$ 。
#include <cstdio>
#include <algorithm>
#define N 1030
using namespace std;
int n , w[N][12] , v[N][12] , f[N][N] , p[12];
void dfs(int x , int d)
{
int i , j;
for(i = 0 ; i <= 1 << d ; i ++ ) f[x][i] = 0;
if(!d)
{
for(i = 1 ; i <= n ; i ++ )
{
if(p[i]) f[x][1] += w[x][i];
else f[x][0] += v[x][i];
}
return;
}
p[d] = 0 , dfs(x << 1 , d - 1) , dfs(x << 1 | 1 , d - 1);
for(i = 0 ; i <= 1 << (d - 1) ; i ++ )
for(j = 0 ; j <= 1 << (d - 1) ; j ++ )
f[x][i + j] = max(f[x][i + j] , f[x << 1][i] + f[x << 1 | 1][j]);
p[d] = 1 , dfs(x << 1 , d - 1) , dfs(x << 1 | 1 , d - 1);
for(i = 0 ; i <= 1 << (d - 1) ; i ++ )
for(j = 0 ; j <= 1 << (d - 1) ; j ++ )
f[x][i + j] = max(f[x][i + j] , f[x << 1][i] + f[x << 1 | 1][j]);
}
int main()
{
int m , i , j , ans = 0;
scanf("%d%d" , &n , &m) , n -- ;
for(i = 0 ; i < (1 << n) ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%d" , &w[i + (1 << n)][j]);
for(i = 0 ; i < (1 << n) ; i ++ ) for(j = 1 ; j <= n ; j ++ ) scanf("%d" , &v[i + (1 << n)][j]);
dfs(1 , n);
for(i = 0 ; i <= m ; i ++ ) ans = max(ans , f[1][i]);
printf("%d\n" , ans);
return 0;
}
最新文章
- http协议
- C++中map的基本操作和使用;
- MySQL优化—工欲善其事,必先利其器之EXPLAIN
- [转]ubuntu错误解决E: Sub-process /usr/bin/dpkg returned an error code (1)
- js基础第二天
- JDBC注册驱动的三种方式
- MongoDB insert/update/one2many案例
- npm常用命令详解
- 演练5-2:Contoso大学校园管理2
- Android编程心得-图片自适应心得
- 乐在其中设计模式(C#) - 命令模式(Command Pattern)
- WCF输出JSON
- mysql-语法大全
- C#生成Guid,SqlServer生成Guid
- HighCharts-动态配置csv格式数据
- 【Selenium-WebDriver自学】WebDriver断言处理(十二)
- Java环境变量配置错误
- Docker容器的原理与实践 (下)
- springboot activiti 整合项目框架源码 shiro 安全框架 druid windows10风格
- TScrollBox响应鼠标滚轮问题
热门文章
- 【洛谷P2016】战略游戏
- 【LOJ10121】与众不同
- NPOI读取Excel到集合对象
- [深度学习] 使用Darknet YOLO 模型破解中文验证码点击识别
- 「Leetcode」976. Largest Perimeter Triangle(C++)
- bootstrap form样式及数据提交
- Towards Accurate Multi-person Pose Estimation in the Wild 论文阅读
- PHP原生代码写的微信扫码支付实例
- 622.设计循环队列 javascript实现
- day-19 多种优化模型下的简单神经网络tensorflow示例