[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 main() printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1947] 笨笨当粉刷匠_NOI导刊2011提高（10）（DP）

下一篇：[luoguP3694] 邦邦的大合唱站队／签到题（状压DP）

---

DP