传送门

先通过二分预处理出来,每个硬币在每个商品处最多能往后买多少个商品

直接状压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;
}

  

最新文章

  1. Kooboo CMS技术文档之三:切换数据存储方式
  2. python学习笔记(python介绍)
  3. C和指针 第九章 字符串 字符 字节
  4. JsonString,字典,模型之间相互转换
  5. mapReduce编程之google pageRank
  6. 以Web Host的方式来寄宿Web API
  7. 实践SQLServer Tuning
  8. July-程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大经典原创系列集锦与总结
  9. c++,命名空间(namespace)
  10. 深入理解ES6之—符号与符号属性
  11. Asp.net core 2.0.1 Razor 的使用学习笔记(一)
  12. gradle配置国内镜像
  13. 阿里云ECS试用配置
  14. MQTT 单片机端讲解
  15. 【待补】splay 模板
  16. hdoj5785
  17. C#中string类型是值类型还是引用类型?(转)
  18. java中 immutable,future,nio
  19. List元素删除不会导致越界但有问题的写法
  20. OpenCV-跟我一起学数字图像处理之拉普拉斯算子

热门文章

  1. P3742 umi的函数
  2. CF962D Merge Equals
  3. 获取登陆信息 在created()方法中
  4. 解决Ueditor在bootstarp 模态框中全屏问题
  5. springboot设置接口超时
  6. env - 在重建的环境中运行程序
  7. 【转载】用Python实现端口映射功能(A/B/C内外网)
  8. linux下的基础操作
  9. python基础一day3 字符串
  10. ProxyFactory