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


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

题解

作者：jzdx（hjh）

题目描述

开始你手里有个硬币，每个硬币的价值在之间（使用顺序没有限制），你准备按 顺序买个物品价格，

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

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

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

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

样例

输入
3 6
12
15
10
6
3
3
2
3
7
输出
12

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

算法

(状压dp + 二分 + 贪心)

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

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

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

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

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

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

状态计算：

1. 初值

2. 对于状态,物品，

   其中&

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

   二分的范围就是

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

最后输出

时间复杂度

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;
}

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

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月15日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴