传送门
先通过二分预处理出来，每个硬币在每个商品处最多能往后买多少个商品
直接状压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 main() printf("%d\n", ans); return 0; }
上一篇：[luoguP1489] 猫狗大战（DP）
下一篇：[luoguP2015] 二叉苹果树（DP）
DP
