题目描述

约翰到商场购物，他的钱包里有K(1 <= K <= 16)个硬币，面值的范围是1..100,000,000。
约翰想按顺序买 N个物品(1 <= N <= 100,000)，第i个物品需要花费ci块钱，(1 <= c(i) <= 10,000)。
在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。
请计算出在购买完N个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1。

输入格式 Input Format

• Line 1: Two integers, K and N.
• Lines 2..1+K: Each line contains the amount of money of one of FJ’s coins.
• Lines 2+K..1+N+K: These N lines contain the costs of FJ’s intended purchases.

输出格式 Output Format

• Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.

输入：

3 6
12
15
10
6
3
3
2
3
7

输出：

12

---

想法

状态压缩入门题目
观察数据范围可知，我们可以枚举硬币的使用状态来获得不同种方式购买可以剩余的最大钱数。
根据题意可知，每一步操作相关的除了硬币的使用外还有购买区间的价值总和。
因此我们定义e[i]表示状态为i的硬币使用状态可以得到的最多商品数，状态转移方程为$e[i]=max(e[j]+num_{i,j})\quad(j=i\oplus 2^{k},k=(1,n))$
其中${num_i,j}$表示从状态j加上第k个硬币转移到的状态i可以增加的商品数目。
我们可以用二分来快速在当前区间(e[j],n)内找到加入该硬币后可以获得的商品个数。由于商品购买区间是连续的，所以我们可以先预处理出前缀和，然后二分时用前缀和处理出区间商品个数来查找。
最后找出可以包含第n个商品的状态，若是没有一个e达到n呢就输出-1，选取出来包含n的计算剩下的硬币钱数，最后取最大值输出即可

#include<bits/stdc++.h>
using namespace std;
int k,n,c[100010],e[100010],coin[70000],d[20];
long long maxn=1,q[100010],maxx=-1,sum,coinnum=0;
inline int er(int l,int r,int i)
{
    int mid=(l+r)/2,ll=l;
    while(l+1<r)
    {
        mid=(l+r)/2;
        if(q[mid]-q[ll]>coin[i])r=mid;
        else l=mid;
    }
    return (((q[r]-q[ll])<=coin[i])?r:l);
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    scanf("%d%d",&k,&n);
    for(int i=1;i<=k;i++)scanf("%d", &coin[i]),coinnum+=coin[i];
    for(int i=1;i<=n;i++){scanf("%d", &c[i]);q[i]=q[i-1]+c[i];}
    for(int i=1;i<=k;i++)maxn*=2;
    d[1]=1;for(int i=2;i<=k;i++)d[i]=d[i-1]<<1;
    for(int i=1;i<=maxn;i++)
    {
        for(int j=1;j<=k;j++)
            if(i&d[j])  
                e[i]=max(e[i],er(e[i^d[j]],n,j));
    }
    for(int i=1;i<=maxn;i++)
    {
        sum=0;
        if(e[i]==n)
        {
            for(int j=1;j<=k;j++)
                if(i&d[j])sum+=coin[j];
            maxx=max(maxx,coinnum-sum);
        }
    }cout<<maxx<<endl;
    return 0;
}