【bzoj3312】[Usaco2013 Nov]No Change 状态压缩dp+二分
题目描述
Farmer John is at the market to purchase supplies for his farm. He has in his pocket K coins (1 <= K <= 16), each with value in the range 1..100,000,000. FJ would like to make a sequence of N purchases (1 <= N <= 100,000), where the ith purchase costs c(i) units of money (1 <= c(i) <= 10,000). As he makes this sequence of purchases, he can periodically stop and pay, with a single coin, for all the purchases made since his last payment (of course, the single coin he uses must be large enough to pay for all of these). Unfortunately, the vendors at the market are completely out of change, so whenever FJ uses a coin that is larger than the amount of money he owes, he sadly receives no changes in return! Please compute the maximum amount of money FJ can end up with after making his N purchases in sequence. Output -1 if it is impossible for FJ to make all of his purchases.
K个硬币,要买N个物品。
给定买的顺序,即按顺序必须是一路买过去,当选定买的东西物品序列后,付出钱后,货主是不会找零钱的。现希望买完所需要的东西后,留下的钱越多越好,如果不能完成购买任务,输出-1
输入
Line 1: Two integers, K and N.
* Lines 2..1+K: Each line contains the amount of money of one of FJ's coins.
* Lines 2+K..1+N+K: These N lines contain the costs of FJ's intended purchases.
输出
* Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.
样例输入
3 6
12
15
10
6
3
3
2
3
7
样例输出
12
题解
状压dp+二分
f[i]表示硬币使用状态为i时最多能购买的物品
那么有f[i]=k (sum[k]-sum[f[i^(1<<j)]]≤v[j])。
然后二分查找求出k即可。
还是注意数组从1开始的问题。
#include <cstdio> #include <algorithm> using namespace std; int f[70000] , v[20] , a[100010] , sum[100010] , cost[70000] , n , base[70000]; int search(int z , int c) { int l = z , r = n , mid , ans = -1; while(l <= r) { mid = (l + r) >> 1; if(sum[mid] - sum[z] <= c) ans = mid , l = mid + 1; else r = mid - 1; } return ans; } int main() { int k , i , j , tmp , ans = -1 , sn = 0; scanf("%d%d" , &k , &n); for(i = 1 ; i <= k ; i ++ ) scanf("%d" , &v[i]) , sn += v[i] , base[1 << (i - 1)] = i; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , sum[i] = sum[i - 1] + a[i]; for(i = 1 ; i < (1 << k) ; i ++ ) { for(j = 1 ; j <= k ; j ++ ) { if((1 << (j - 1)) & i) { tmp = search(f[i ^ (1 << (j - 1))] , v[j]); if(tmp != -1) f[i] = max(f[i] , tmp); } } } for(i = 1 ; i < (1 << k) ; i ++ ) { cost[i] = cost[i - (i & (-i))] + v[base[i & (-i)]]; if(f[i] == n) ans = max(ans , sn - cost[i]); } printf("%d\n" , ans); return 0; }
相关文章
- Android开发之Mediaplayer状态转换图及音频焦点
- thrift.transport.TTransport.TTransportException: Could not start SASL: Error in sasl_client_start (-4) SASL(-4): no mechanism available: No worthy mechs found
- No section matches selector - no section to be FIRST/LAST
- Solidworks如何让齿轮运动副保证持续啮合状态
- TNS-12541: TNS:no listener TNS-12560 TNS-00511: No listener
- Keepalived集群软件高级使用(工作原理和状态通知)
- [AngularJS]8. No images, no gallery, ng-show
- 微信小程序----全局状态管理 (便于全局埋点等操作)
- Hibernate持久化对象三种状态
- 使用JDK自带的jmap和jhat监控处于运行状态的Java进程
- Linux的进程状态
- Atitit 持久化 Persistence概念的艺术 目录 1. 持久化是将程序数据在持久状态和瞬时状态间转换的机制。1 2. DBC就是一种持久化机制。文件IO也是一种持久化机制。2 3.
- IOS No devices because active scheme has no targets
- Flutter高级第4篇:inappbrowser、StatefulBuilder 更新 Flutter showDialog、showModalBottomSheet中的状态
- 查看http的并发请求数与其TCP连接状态
- ORA-06575: 程序包或函数 NO_VM_DROP_PROC 处于无效状态
- Linux基础命令-stat显示文件的状态信息
- 虚拟机网卡重启报错:Error: No suitable device found: no device found for connection 'System eth0'
- Android Stdudio 打包Apk签名时出现状态窗口报错提示:Please select at least one of the signature versions to use
- Linux 案例分析不可中断状态和僵尸状态进程
- Pod 一直处于 Pending 状态
- 计算机获取不到动态绑定的IP地址一直在获取又断开状态无法正常上网