BZOJ-3312: [Usaco2013 Nov]No Change

Description

K个硬币，要买N个物品。给定买的顺序，即按顺序必须是一路买过去，当选定买的东西物品序列后，付出钱后，货主是不会找零钱的。现希望买完所需要的东西后，留下的钱越多越好，如果不能完成购买任务，输出-1。K<=16 N<=100000

状压DP。
dp[s]表示用了状态为s的硬币能买的最长前缀的长度，预处理前缀和每次二分转移即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int k,n,c[20],w[101000],ans=-1,dp[1<<17];
int calc(int x)
{
    int l=0,r=n+1,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(w[mid]<=x) l=mid+1;
        else r=mid;
    }
    return l-1;
}
int main()
{
    scanf("%d%d",&k,&n);
    for(int i=0;i<k;++i) scanf("%d",c+i);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",w+i);
        w[i]+=w[i-1];
    }
    for(int s=0;s<(1<<k);++s)
    {
        for(int i=0;i<k;++i) if(!((s>>i)&1))
            dp[s|(1<<i)]=max(dp[s|(1<<i)],calc(w[dp[s]]+c[i]));
        if(dp[s]==n)
        {
            int tmp=0;
            for(int i=0;i<k;++i) if(!((s>>i)&1)) tmp+=c[i];
            ans=max(ans,tmp);
        }
    }
    printf("%d",ans);
    return 0;
}