自动搬运

查看原文

来自洛谷，原作者为

	jun1lesszZZ I AK CSP

搬运于2025-08-24 21:45:14，当前版本为作者最后更新于2019-08-16 09:48:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

状压$DP$ + 二分

考虑构成：$k<=16$所以根据$k$构造状压$dp$，将所有硬币的使用情况进行状态压缩

考虑状态：数组$dp[i]$表示用$i$状态下的硬币可以购买到第几个商品 ，$f[i]$表示状态$i$下的花费

考虑转移：使用当前硬币的状态一定由使用上一个硬币的状态转移而来

举个例子：

• 之前状态$x$：$dp[x] = y$， $i = 2 = (010)_2$

• 当前枚举到的状态$i = 3 = (011)_2$ , $dp[i] = (dp[x] + 1$开始能买到哪里$(<=n))$, 相当于状态$x$能购买到$y$号物品，$i$要从$y+1$号开始购买

• $i$状态比$x$状态在二进制的第三位多了1，说明比i状态多用了一个编号为1的硬币，$f[i] = f[x]$ + 硬币$1$的价值

• 状态转移完成

考虑具体做法：外层循环枚举所有状态，内层循环枚举每一位，若当前状态$i$的第$j$位为$1$，则可以进行转移

然后可以进行枚举$n$件物品，考虑每一件是否可以购买，一直到不能购买为止

因为一种状态可以被更新多次，所以要取$max$，保证$dp$数组存的是能买到的最大编号，然后更新$dp$数组和$f$数组

如果到第$n$件都可以买，则可以购买全部物品，$ans$记录当前的最小花费，最后用所有硬币的总面值减去最小花费即为答案

如果$ans$没有被更新过，说明不能购买，输出$-1$

时间复杂度$O(2^kkn)$，超时

考虑优化：发现每次枚举物品统计价值来检查是否能够购买是冗余操作，可以用前缀和预处理一下，然后每次检查的时候进行一次二分就可以了

时间复杂度$O(2^kklogn)$，可通过本题

考虑正确性：因为外层循环枚举状态是从小到大枚举，所以保证当前状态某一位少$1$(即当前使用硬币数减一)的状态已经被转移过了

注意事项：
1.不要错误理解题意，注意每次支付只能支付一枚硬币 ，不能算把硬币凑出来的总钱数然后判断能购买多少，这种错误做法能拿到$93$分的好成绩(大雾)是因为数据太水

2.二分的时候注意初始的左端点，因为从使用当前硬币的状态转移过来，所以要从使用当前硬币前状态所能购买到的物品$+1$作为左端点进行二分，右端点不会变化一直是$n$

3.因为二分时要检查的值要与前缀和数组进行比较，所以比较时前缀和数组应该减去左端点之前的前缀

4.注意二分的边界问题以及最后的返回值

代码：

#include <cstdio>
#include <cctype>
#define min(a, b) a < b ? a : b
#define MAXN 100001
#define N 17

int n, m, tot_money, ans = 2147483647;
int dp[1 << N], f[1 << N], sum[MAXN], pay[MAXN], coin[MAXN];

inline int read() {
    int s = 1, w = 0; char ch = getchar();
    for(; ! isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = w * 10 + ch - '0';
    return s * w;
}
inline int check(int x, int cha) {
	int l = cha, r = n, mid;
	while(l <= r) {
	  mid = (l + r) >> 1;
	  if(sum[mid] - sum[cha - 1] == x) return mid;
	  if(sum[mid] - sum[cha - 1] < x) l = mid + 1;
	  else r = mid - 1;
	}
	return r;
}

int main() {
	m = read(), n = read();
	for(int i = 1; i <= m; i ++) coin[i] = read(), tot_money += coin[i];
	for(int i = 1; i <= n; i ++) pay[i] = read(), sum[i] = sum[i - 1] + pay[i];
	for(int i = 1; i < (1 << m); i ++) {
	  for(int j = 0; j < m; j ++) if(i & (1 << j)) {
	    int x = (i ^ (1 << j)), sum;
      if((sum = check(coin[j + 1], dp[x] + 1)) > dp[i]) 
        dp[i] = sum, f[i] = f[x] + coin[j + 1];
		  if(dp[i] == n) ans = min(f[i], ans);
	  } 
	}
	printf("%d", (tot_money - ans) < 0 ? -1 : tot_money - ans);
	return 0;
}