Description
约翰带着 N 头奶牛在超市买东西，现在他们正在排队付钱，排在第 i 个位置的奶牛需要支付 Ci元。今天说好所有东西都是约翰请客的，但直到付账的时候，约翰才意识到自己没带钱，身上只有 K张消费卡，第 i 张卡里有 Vi 元余额。
问题是，这些消费卡都是一次性的，它们可以被收银机读取，但如果卡一旦离开了收银机，卡里的余额就会归零，而且超市也不负责找零！奶牛的队伍很长，不可能再调整她们的位置了，所以一张卡只能支付一段连在一起的账单。而且，一张账单只能用一张消费卡支付，超市的系统不接受用两张或以上的卡支付一笔账单。
约翰的问题就是按照什么样的顺序来使用这些消费卡，才能让他能为所有的奶牛买单，而且使得剩余的消费卡的余额之和最大呢？
Input Format
• 第一行：两个整数 K 和 N ，1 ≤ K ≤ 16, 1 ≤ N ≤ 10^5
• 第二行到第 K + 1 行：第 i + 1 行有一个整数 Vi，1 ≤ Vi ≤ 10^9
• 第 K + 2 行到第 K + N + 1 行：第 i + K + 1 行有一个整数 Ci，1 ≤ Ci ≤ 10^4
Output Format
单个整数：表示约翰买完所有奶牛的单之后，最多还能剩多少余额，如果他带的卡根本没有办法支付所有的账单，输出 −1。
Solution
发现K范围小，考虑状压DP，设\(F[S]\)表示所以消费卡状态为S时可以到达最后面的奶牛编号，即前面的奶牛都付完，
在二进制下1表示用过了，0表示没有
那么\(F[S|2^{k-1}]=max\{Get(card(k),F[S]+1)\}\) ,
\(Get(s,pos)\) 表示可用金额为s, 从\(Cow_{pos}\) 可到达最远的奶牛坐标，
那么Get函数可以用前缀和+二分查找优化，否则会超时
这题挂了好几次，
- 写了前缀和，后面忘记写二分查找
- 没有用max！WA了，居然还过了好多点
Code
#include#include #define N 100010using namespace std;int n, k, card[19], sum[N], cow[N], f[1 << 19], Ans;inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f;}inline int get(int k, int st) { int l = st, r = n, res; while (l <= r) { int mid = (l + r) >> 1; if (sum[mid] - sum[st - 1] <= k) res = mid, l = mid + 1; else r = mid - 1; } return res;}inline int cnt(int S) { int r = 0; for (int i = 1; i <= k; ++i) if (!(S & (1 << (i - 1)))) r += card[i]; return r;}int main() { k = read(), n = read(); for (int i = 1; i <= k; ++i) card[i] = read(); for (int i = 1; i <= n; ++i) { cow[i] = read(); sum[i] = sum[i - 1] + cow[i]; } Ans = -1; for (int S = 0; S < (1 << k); ++S) { if (f[S] == n) continue; for (int i = 1; i <= k; ++i) { int T = (1 << (i - 1)); if (S & T) continue; f[S | T] = max(f[S | T], get(card[i], f[S] + 1)); if (f[S | T] == n) Ans = max(Ans, cnt(S | T)); } } printf("%d\n", Ans); return 0;}