洛谷P3092 [USACO13NOV] No Change G 题解

题意：

Farmer John 在市场上为他的农场购买物资。他的口袋里有 $k$ 个硬币 $(1 \le k \le 16)$ ，每个硬币的价值在$1\sim 10^8$ 范围内。 FJ 想进行一连串的 $n$ 次购买 $(1 \le n \le 10^5)$ ，其中第 $1$ 次购买需要花费 $c_i$ 个单位的钱$(1 \le c_i \le 10^4)$ 。当他进行这一连串的购买时，他可以定期停下来，用一枚硬币来支付自他上次付款以来的所有购买（当然，他使用的这枚硬币必须足够大，以支付所有这些购买）。不幸的是，市场上的小贩完全没有零钱，所以每当 FJ 使用大于他所欠的钱的硬币时，他都很遗憾地没有收到任何零钱的回报！请计算出最大的金额。

请计算 FJ 在依次进行了 $n$ 次购买后，最终能得到的最大金额。如果 FJ 不可能完成他所有的购买，则输出 $-1$。

输入格式：

第 $1$ 行，两个整数，$k$ 和 $n$ 。

第 $2\ \sim \ k+1$ 行，每一行包含 FJ 的一个硬币的金额。

第 $2+k\ \sim \ n + k + 1$ 行，这 $n$ 行包含 FJ 打算购买的东西的费用。

输出格式：

第1行，FJ 最终能得到的最大金额，如果 FJ 不能完成所有的购买，则输出 $-1$。

得到的最大金额一定时，硬币的状态不唯一，因此不能二分。

于是考虑枚举所有的状态，但是每次都暴力检验复杂度太高了

注意到很多的状态之间存在联系，比如某个状态不能成功购买，但是后面加上了几个硬币就能买了

设 $f_i$ 表示状态为 $i$ 时最多能买到几号物品。不妨记每个硬币的面额为 $v_i$ 。

状态可以转移至 $f_j$ 当且仅当 $j = i\, \cup\,\{k\},~k \in (\sim i)$ 。记 $r=p$ 为使得 $\sum_{t = f_i}^{r} v_t \le w_k$ 成立的最大值，则

$f_j \uparrow p$

这个 $p$ 可以二分得到，只需要预处理下 $v_i$ 的前缀和。并且当某个 $f_i = n$ 时，尝试更新一下当前的答案。

时间复杂度 $\mathcal{O}(2^kk \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define M ((int)((1 << 16) + 16))

int n,k,res,sum[N],mon[N],f[M];
int find(int l,int r,int s)
{
    for(int mid, now = sum[l]; l < r; )
    {
        mid = (l + r + 1) >> 1;
        if(sum[mid] - now <= s) l = mid; else r = mid - 1;
    }
    return l;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    
    cin >> k >> n;
    for(int i = 1; i <= k; i++) cin >> mon[i];
    for(int i = 1; i <= n; i++) { cin >> sum[i], sum[i] += sum[i - 1]; }
    int mx = (1ll << k) - 1, ok = 0;
    for(int i = 0; i <= mx; i++)
    {
        for(int j = 0; j < k; j++)
        {
            if((i >> j) & 1) continue;
            up(f[i | (1ll << j)], find(f[i], n, mon[j + 1]));
        }
        if(f[i] == n && (ok = 1))
        {
            int cnt = 0;
            for(int j = 0; j < k; j++)
                if(((i >> j) & 1) == 0) cnt += mon[j + 1];
            up(res, cnt);
        }
    }
    cout << (ok ? res : -1) << '\n';
    return 0;
}