【每日一题】2021年4月8日题目精讲

题号 NC24416
名称不用找了
来源 USACO
每日一题三期汇总贴~

如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jzdx（hjh）

题目描述

开始你手里有 $K$ 个硬币，每个硬币的价值 $w[i]$ 在 $[1 , 100000000]$ 之间（使用顺序没有限制），你准备按顺序买 $N$ 个物品价格 $v[i]$ ，

但是商店没有足够的零钱，所以如果你花费的费用超过了买的物品的价值，商店是不会找零的。

你可以选择任意的连续的 $[L,R]$ 的物品进行付款（前提是 $[L,R]$ 的物品的价格总和小于等于你要花费的硬币的价值），

问如何合理的安排硬币的使用顺序以及每个硬币购买哪些物品可以使得最后买完n个物品后手里剩下的硬币的价值最大，

输出最大价值，如果不能买完所有n个物品输出-1。

样例

富坚拥有3个价值为12、15和10的硬币。他必须
按价值6、3、3、2、3和7的顺序进行购买。
富坚在第一次用价值为10的硬币。购买前两个物品(6,3)，然后
用价值为15的硬币买剩下的物品，他最后剩下了价值为12的硬币

算法

(状压dp + 二分 + 贪心)

我们考虑一个存在性问题：

是否存在一种使用硬币的合法方案将所有 $N$ 个物品买完

要解决这个问题，首先我们考虑从所有硬币中选取一些硬币，这些硬币能按顺序购买的最多的物品个数是多少

如果购买的最多的物品个数等于 $N$ 则说明选择的这些硬币一定能构造出一个合法的购买方案，否则不能

我们发现硬币的个数最多只有 $16$ 个提醒我们用状态压缩dp来求

状态表示： $f[i]$ 表示硬币使用状态为i，用选取的硬币按顺序购买的最多物品个数是多少

状态计算： $(sum表示物品价值的前缀和)$

初值 $f[0] = 0,其余f[i] = -INF$
对于状态 $i$ ,物品 $j$ ， $f[i] = max(f[i],k)$

其中 $(i >> j$ & $1 == 1) 且k为最大的满足sum[k] - sum[f[i - (1 << j)]] <= w[j] 的数$

我们发现购买的区间长度与价格之和有两段性(区间越长价格之和越大，区间越短价格之和越小)所以 $k$ 可以用二分求

二分的范围就是 $[f[i - (1 << j)],n]$

得到 $f$ 数组后我们枚举所有状态，如果 $f[i] = n$ 则通过状态 $i$ 计算使用的硬币的价值，进而求出剩余硬币的价值，用变量 $res$ 维护一个最大值

最后输出 $res$

时间复杂度 $O(K * log(N) * 2^K)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
const int N = 100010, M = (1 << 16) + 10,INF = 0x3f3f3f3f;
int f[M];
int coin[20];
int s[N];
int sum;
int n,m;

int find(int x,int k)
{
    int l = x,r = n;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(s[mid] - s[x] <= k) l = mid;
        else r = mid - 1;
    }
    return l;
}

int calc(int state)
{
    int res = sum;
    for(int i = 0;i < m;i ++) 
        if(state >> i & 1)
            res -= coin[i];
    return res;
}

void solve()
{
    scanf("%d%d",&m,&n);
    for(int i = 0;i < m;i ++ )
    {
        scanf("%d",&coin[i]);
        sum += coin[i];
    }
    for(int i = 1;i <= n;i ++ ) scanf("%d",&s[i]);
    for(int i = 1;i <= n;i ++ ) s[i] += s[i - 1];
    memset(f,-0x3f,sizeof f);
    f[0] = 0;
    for(int i = 0;i < 1 << m;i ++)
    {
        for(int j = 0;j < m;j ++)
        {
            if(i >> j & 1)
            {
                if(f[i - (1 << j)] >= 0)
                    f[i] = max(f[i],find(f[i - (1 << j)],coin[j]));
            }
        }
    }
    int res = -1;
    for(int i = 0;i < 1 << m;i ++)
    {
        if(f[i] == n)
            res = max(res,calc(i));
    }
    printf("%d\n",res);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(N - 1);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！