【每日一题】2021年4月8日题目 No Change

题号 NC24416
名称 不用找了
来源 USACO

题目描述

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

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

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

问如何合理的安排硬币的使用顺序以及每个硬币购买哪些物品可以使得最后买完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;
}