状压\(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;
}

巴特西

[洛谷P3092]【[USACO13NOV]没有找零No Change】

状压\(DP\) + 二分

最新文章

热门文章