洛谷 P3092 [USACO13NOV] No Change G 题解

题目描述

约翰到商场购物，他的钱包里有K(1 <= K <= 16)个硬币，面值的范围是1…100,000,000。

约翰想按顺序买 N个物品(1 <= N <= 100,000)，第i个物品需要花费c(i)块钱，(1 <= c(i) <= 10,000)。

在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

请计算出在购买完N个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1

思路（前置知识：状态压缩动态规划， 二分）

考虑状态压缩动态规划。

设 $f_i$ 为选择状态为 $i$ 的硬币，能覆盖从 $1$ 开始的最多的硬币的硬币数。

我们把最低位设为 $0$，最高位设为 $k-1$，用第 $i$ 位表示硬币 $i$ 是否选上，可得到状态转移方程：

$f_i=\underset{j=0}{\overset{k,i的第j位是1}{\max }}cnt(f_j+1,c[j])$

其中 $cnt(i,j)$ 表示从第 $i$ 个物品开始，花 $j$ 面值的硬币依次买物品，能买到的最大下标。

最后计算答案的时候，把所有 $f_i=n$ 的方案算在答案里，把没用过的硬币状态的硬币的面值加在一起。取 $\max$ 就可以了。

无解也好判断，如果没有状态 $f_i=n$，则无解。

$cnt$ 函数枚举求 $O(n)$，状态数 $2^k$，转移 $O(k)$。当前总时间复杂度 $O(2^{k}kn)$。无法通过本题。

我们考虑优化求 $cnt$ 函数，我们发现它可以二分求。每次二分答案 $mid$，如果从最开始到 $mid$ 的物品价值总和 $<=$ 硬币面值，则说明答案在 $\ge mid$；如果从最开始到 $mid$ 的物品价值总和 $>$ 硬币面值，则说明答案在 $<mid$。

代码 + 运行效率

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, K = 16;

int n, k;
int a[N];
int c[K];
int f[1 << K], g[1 << K];

int check(int L, int c)
{
int l = L - 1, r = n;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid] - a[L - 1] <= c) l = mid;
else r = mid - 1;
}
return r;
}

int main()
{
scanf("%d%d", &k, &n);
int sum = 0;
for (int i = 0; i < k; i ++ )
{
scanf("%d", &c[i]);
sum += c[i];
}
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
a[i] += a[i - 1];
}

for (int i = 1; i < 1 << k; i ++ )
for (int j = 0; j < k; j ++ )
if (i & (1 << j))
{
int t = i ^ (1 << j);
f[i] = max(f[i], check(f[t] + 1, c[j]));
}

int res = -2e9;
for (int i = 1; i < 1 << k; i ++ )
if (f[i] == n)
{
int val = 0;
for (int j = 0; j < k; j ++ )
if (i & (1 << j))
val += c[j];
res = max(res, sum - val);
}

if (res == -2e9) puts("-1");
else printf("%d\n", res);

return 0;
}

原文地址：https://blog.csdn.net/mkx2023275/article/details/142831293

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！