[USACO13NOV]没有找零No Change

洛咕

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

分析:\(k<=16\),状压\(!!!\)设\(f[i]\)表示当前当前已经用了的硬币集合为i时能够买到的最多的物品数(因为题目要求物品必须要按顺序买,所以一个硬币买到的一定是一段连续物品).

\(f[i]=max(f[i],calc(f[i\)&\((1<<(j-1))],c[j]))\)(表示当前选择用第\(j\)枚硬币去买东西),\(mmp\),转移的时候忘记取\(max\)调了一上午.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
int n,m,ans=-1,tot,maxn,bj;
int a[20],b[N],f[N],sum[N];
inline int calc(int x,int y){通过前缀和,二分答案,找到用这枚硬币能够买到的最多的物品
    if(x==m)return m;
    int l=x+1,r=m,pos=x;
    while(l<=r){
        int mid=(l+r)>>1;
        if(sum[mid]-sum[x]<=y)pos=mid,l=mid+1;      
        else r=mid-1;
    }
    return pos;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read(),tot+=a[i],maxn=max(maxn,a[i]);
    for(int i=1;i<=m;++i)b[i]=read(),sum[i]=sum[i-1]+b[i];
    for(int i=1;i<=m;++i)if(maxn<b[i]){puts("-1");return 0;}
    if(tot<sum[n]){puts("-1");return 0;}//两个特判.
    for(int j=1;j<(1<<n);++j)
        for(int i=1;i<=n;++i)
            if(j&(1<<(i-1)))f[j]=max(f[j],calc(f[j^(1<<(i-1))],a[i]));//记得取max!
    for(int j=1;j<(1<<n);++j){
        if(f[j]==m){
            int cnt=tot;
            for(int i=1;i<=n;++i)if(j&(1<<(i-1)))cnt-=a[i];
            ans=max(ans,cnt);
        }
    }
    printf("%d\n",ans);
    return 0;
}

[USACO13NOV]没有找零No Change

原文：https://www.cnblogs.com/PPXppx/p/11726009.html