---

题目传送门

---

前言

别人说这是道简单题，随便搞搞就过了。但我并不觉得 （光状态设计第一步就被卡住了），pdf 了。颓题解了，写篇题解谢罪。

---

状态设计

设 $d{p}_i$ 表示硬币状态为 $i$ 的情况下，最多可以买到第几个物品 （非常创新的状态设计）。

---

状态转移

枚举当前硬币状态，由于每次只能使用一枚硬币，所以当前状态一定只比上一个状态多使用了一个硬币。
因此枚举当前状态的每一位，得出上个状态 $j$。

对于物品的价格做完前缀和后，二分在 $[d{p}_j+1,n]$ 区间的物品，找到最后一个满足 $s{c}_{pos}-s{c}_{d{p}_j}$ 的 $pos$。让 $pos$ 与 $d{p}_i$ 取 $max$ 即可。

---

答案

将 $ans$ 初始化为 $-1$，这样如果它没被更新就说明无解。

若 $d{p}_i=n$，即在此状态 $i$ 下可以买到最后一个物品，那就将此状态对应的花费 $s{m}_i$ 与 $ans$ 取 $max$ 即可。

---

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const int maxs = (1 << 16) + 7;
const int inf  = 0x3f3f3f3f;

int n, m, ms;
int mon[27], c[maxn];
int sc[maxn], sm[maxs];
int dp[maxs];
int ans = -1;
void print(int x) {
	for (int i = 0; i < m; ++i)
		if (x & (1 << i)) putchar('1');
		else putchar('0');
}
int main() {
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= m; ++i)
		scanf("%d", mon + i);
	for (int i = 1; i <= n; ++i)
		scanf("%d", c + i),
		sc[i] = sc[i - 1] + c[i];
	ms = (1 << m) - 1;
	for (int s = 0; s <= ms; ++s)
		for (int i = 0; i < m; ++i)
			if (s & (1 << i)) sm[s] += mon[i + 1];
	for (int s = 0; s <= ms; ++s) {
		for (int j = 0; j < m; ++j) {
			if (!(s & (1 << j))) continue;
			int lsts = s ^ (1 << j);
//			if (c[dp[lsts] + 1] > sm[s] - sm[lsts])
//				continue;
			int l = dp[lsts] + 1, r = n, pos = 0;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (sc[mid] - sc[dp[lsts]] <= sm[s] - sm[lsts])
					pos = mid, l = mid + 1;
				else r = mid - 1;
			}
			dp[s] = max(dp[s], pos);
//			for (int i = dp[lsts] + 1; i <= n; ++i)
//				if (sc[i] - sc[dp[lsts]] <= sm[s] - sm[lsts])
//					dp[s] = max(dp[s], i);
		}
		if (dp[s] == n)
			ans = max(ans, sm[ms] - sm[s]);
	}
	printf("%d\n", ans);
//	for (int s = 0; s <= ms; ++s)
//		printf("sm["), print(s), printf("] = %d\n", sm[s]);
//	for (int s = 0; s <= ms; ++s)
//		printf("dp["), print(s), printf("] = %d\n", dp[s]);
	return 0;
}

时间复杂度 $O(k\times 2^k\times log(n))$。