题解 P3092 【[USACO13NOV]没有找零No Change】

· · 题解

状压DP + 二分

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

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

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

举个例子：

考虑具体做法：外层循环枚举所有状态，内层循环枚举每一位，若当前状态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;
}