[luoguP3092] [USACO13NOV]没有找零No Change(状压DP + 二分)
2024-09-07 14:38:45
先通过二分预处理出来,每个硬币在每个商品处最多能往后买多少个商品
直接状压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;
}
最新文章
- Kooboo CMS技术文档之三:切换数据存储方式
- python学习笔记(python介绍)
- C和指针 第九章 字符串 字符 字节
- JsonString,字典,模型之间相互转换
- mapReduce编程之google pageRank
- 以Web Host的方式来寄宿Web API
- 实践SQLServer Tuning
- July-程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大经典原创系列集锦与总结
- c++,命名空间(namespace)
- 深入理解ES6之—符号与符号属性
- Asp.net core 2.0.1 Razor 的使用学习笔记(一)
- gradle配置国内镜像
- 阿里云ECS试用配置
- MQTT 单片机端讲解
- 【待补】splay 模板
- hdoj5785
- C#中string类型是值类型还是引用类型?(转)
- java中 immutable,future,nio
- List元素删除不会导致越界但有问题的写法
- OpenCV-跟我一起学数字图像处理之拉普拉斯算子