【bzoj1688】[USACO2005 Open]Disease Manangement 疾病管理 状态压缩dp+背包dp
题目描述
Alas! A set of D (1 <= D <= 15) diseases (numbered 1..D) is running through the farm. Farmer John would like to milk as many of his N (1 <= N <= 1,000) cows as possible. If the milked cows carry more than K (1 <= K <= D) different diseases among them, then the milk will be too contaminated and will have to be discarded in its entirety. Please help determine the largest number of cows FJ can milk without having to discard the milk.
输入
* Line 1: Three space-separated integers: N, D, and K * Lines 2..N+1: Line i+1 describes the diseases of cow i with a list of 1 or more space-separated integers. The first integer, d_i, is the count of cow i's diseases; the next d_i integers enumerate the actual diseases. Of course, the list is empty if d_i is 0. 有N头牛,它们可能患有D种病,现在从这些牛中选出若干头来,但选出来的牛患病的集合中不过超过K种病.
输出
* Line 1: M, the maximum number of cows which can be milked.
样例输入
6 3 2
0---------第一头牛患0种病
1 1------第二头牛患一种病,为第一种病.
1 2
1 3
2 2 1
2 2 1
样例输出
5
题解
状态压缩dp+背包dp
f[i]表示i状态时
不预处理num数组应该也行,尽管常数大些,反正都是一道水题
#include <cstdio> #include <algorithm> using namespace std; int f[32770] , num[32770]; int main() { int n , d , k , i , j , x , y , ans = 0 , s; scanf("%d%d%d" , &n , &d , &k); for(i = 1 ; i < (1 << d) ; i ++ ) { num[i] = num[i - (i & (-i))] + 1; } for(i = 1 ; i <= n ; i ++ ) { s = 0; scanf("%d" , &x); while(x -- ) { scanf("%d" , &y); s |= 1 << (y - 1); } for(j = (1 << d) - 1 ; j >= 0 ; j -- ) { if(num[j | s] <= k) { f[j | s] = max(f[j | s] , f[j] + 1); ans = max(ans , f[j | s]); } } } printf("%d\n" , ans); return 0; }
相关文章
- 由易信界面——谈谈fragment 状态的保存
- HostMonitor监控主机状态
- 解密函数计算异步任务能力之「任务的状态及生命周期管理」
- android 中怎么保存当前按钮的状态?就是退出后重新进入还是上一次离开的状态
- Flutter 陈航 10-状态 State 编程范式 构建过程
- Spark Streaming 1.6 流式状态管理分析
- Flink(31):Flink中的状态管理(下)
- reactjs全局状态管理:redux介绍
- SAP CRM订单状态管理的一些重要的数据库表
- S/4HANA生产订单的标准状态和透明工厂原型状态的映射
- Atitit 视图状态ViewState)的原理与管理
- 使用 Pinia 轻松实现复杂的 Vue 3 状态管理
- Android LinearLayout实现类似Button的点击效果且保留状态
- 【状态估计】将变压器和LSTM与卡尔曼滤波器结合到EM算法中进行状态估计(Python代码实现)
- 单元格中输入数据时,QTextEdit如何直接进入编辑状态
- VB编程:利用控件数组设置控件状态-38
- 【Linux 内核】进程管理 ( 进程状态 | 进程创建 | 进程终止 | 调用 exit 系统调用函数主动退出 | main 函数返回自动退出 | kill 杀死进程 | 执行异常退出 )
- Namespace 无法删除一直处于 Terminating 状态
- 管理加速键和焦点矩形的 UI 状态
- QPushButton 控制两种状态
- 大数据Hadoop之——Flink的状态管理和容错机制(checkpoint)
- 传输层 TCP连接管理 建立TCP连接/状态/变迁
- Kubernetes kubelet 状态上报/节点资源的管理
- Kubelet 状态上报 节点资源管理 驱逐
- Kubelet 如何管理 Kubernetes 集群状态以实现高可用性