首页 > 代码库 > [luoguP3092] [USACO13NOV]没有找零No Change（状压DP + 二分）
[luoguP3092] [USACO13NOV]没有找零No Change（状压DP + 二分）
传送门
先通过二分预处理出来，每个硬币在每个商品处最多能往后买多少个商品
直接状压DP即可
f[i]就为，所有比状态i少一个硬币j的状态所能达到的最远距离，在加上硬币j在当前位置所能达到的距离，所有的取max
是满足最优解性质的
#include <cstdio>#include <iostream>#include <algorithm>#define N 17#define max(x, y) ((x) > (y) ? (x) : (y))int n, k, s1, s2, ans = -1;int a[N], sum[100001], c[N][100001], f[1 << N];inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; return x * f;}int main(){ int i, j; k = read(); n = read(); for(i = 1; i <= k; i++) a[i] = read(), s1 += a[i]; for(i = 1; i <= n; i++) sum[i] = read() + sum[i - 1]; for(i = 1; i <= k; i++) for(j = 1; j <= n; j++) c[i][j] = std::upper_bound(sum + j, sum + n + 1, a[i] + sum[j - 1]) - sum - 1; for(i = 1; i < (1 << k); i++) for(j = 1; j <= k; j++) if(i & (1 << j - 1)) f[i] = max(f[i], c[j][f[i ^ (1 << j - 1)] + 1]); for(i = 1; i < (1 << k); i++) if(f[i] == n) { s2 = 0; for(j = 1; j <= k; j++) if(i & (1 << j - 1)) s2 += a[j]; ans = max(ans, s1 - s2); } printf("%d\n", ans); return 0;}
[luoguP3092] [USACO13NOV]没有找零No Change（状压DP + 二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。