[USACO13NOV]No Change

题目大意：
　　你有k(k<=16)个硬币，每个硬币都有自己的面值。
　　现在你要给n件商品付钱，每件商品也有自己的价格。
　　然而老板是个奸商，他绝对不会给你找钱。
　　你每次付钱只能用一个硬币，但是你可以一次性买很多商品。
　　问你最后最多还能留下多少钱。

思路：
　　状压DP。
　　f[i]表示状态为i时能买的商品数，i表示你用了哪些硬币。
　　从小到大枚举每个状态i，然后枚举状态i中的硬币j，是这次付款用的硬币。
　　二分找一下这些硬币最多能买前面连续的多少个商品。
　　如果j不在i中，就算作最后剩下的硬币。

#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int K=16,N=100001;
int v[K],sum[N],f[1<<K];
int main() {
    const int k=getint(),n=getint();
    for(register int i=0;i<k;i++) {
        v[i]=getint();
    }
    for(register int i=1;i<=n;i++) {
        sum[i]=sum[i-1]+getint();
    }
    int ans=-1;
    for(register int i=0;i<(1<<k);i++) {
        int rem=0;
        for(register int j=0;j<k;j++) {
            if(i&(1<<j)) {
                f[i]=std::max(f[i],int(std::upper_bound(&sum[0],&sum[n+1],sum[f[i^(1<<j)]]+v[j])-sum-1));
            } else {
                rem+=v[j];
            }
        }
        if(f[i]==n) {
            ans=std::max(ans,rem);
        }
    }
    printf("%d
",ans);
    return 0;
}