「CJOJ1427」「USACO NOV」不设找零

Problem

Description

FJ正在市场上为他的农场采购日用品，他口袋里有K(1<=K<=16)个硬币，每一个硬币的面值均在1～1,000,000,000之间。FJ有一个包含N(1<=N<=100,000)种待购物品的序列清单，其中第i种物品需要的钱数为c(i)，（1<=c(i)<=10,000），在购物的过程中，他随时可以停下来用一枚硬币付一次钱，每次付钱的对象为从上次付钱之后至当前所有物品价值和（当然，他所付的硬币面值也必须足够大），不巧的是，市场上的商户们都没有零钱了，因此如果FJ给的硬币面值大于所购物品价值，他也不会得到找零！
请计算FJ完成N件物品的购物后，所能剩下的最大钱数。如果他无法买到所有物品，输出-1。

Input

第1行：两个整数K，N；
第2～K+1行：每行为一个硬币面值；
第K+2～N+K+1行：这N行为FJ所要购买的N件物品的价值。

Output

一行，即结束购物后FJ所剩余的最大钱数，输出-1表示他无法完成购物。

Sample Input

3 6
12
15
10
6
3
3
2
3
7

Sample Output

Hint

输出解释：
FJ花费面值为10的硬币购买前两件物品，然后花费面值为15的硬币购买剩余的4样物品，最后剩余一枚面值为12的硬币。

Solution

思路

我们先想到既然k这么小,可以压状态,对于每一枚硬币都是取或者不取,然后就可以愉快的写出如下一些东西:
设f[i]表示用i这个组合的硬币对于上一次可以搞的最远距离,g[i]表示用这个组合搞出来的最大剩余.
然后就发现:f[i]可以用二分查找优化更新,g[i]随着更新就好了.

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
#define ll long long
#define re register
inline int gi(){
    int sum=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
int k,n,sum[1000010],ar[1000010],coin[1000010],f[1000010],g[1000010],ans=-1;
int find(int from,int x){
    int l=from,r=n+1,wz;
    while(l<=r){
        int mid=(l+r)>>1;
        if(sum[mid]-sum[from]<=x){
            wz=mid;l=mid+1;
        }
        else r=mid-1;
    }
    return wz;
}
int main(){
    k=gi();n=gi();
    for(re int i=1;i<=k;i++)coin[i]=gi();
    for(re int i=1;i<=k;i++)g[0]+=coin[i];
    for(re int i=1;i<=n;i++){ar[i]=gi();sum[i]=sum[i-1]+ar[i];}sum[n+1]=2147483647;
    for(re int i=1;i<(1<<16);i++){
        for(re int j=1;j<=16;j++)
            if(i&(1<<j-1)){
                int c=find(f[i-(1<<(j-1))],coin[j]);
                if(c>f[i] || (c==f[i] && g[i-(1<<(j-1))]-coin[j]>g[i])){
                    g[i]=g[i-(1<<(j-1))]-coin[j];f[i]=c;
                }
            }
        if(f[i]==n && g[i]>ans)ans=g[i];
    }
    printf("%d
",ans);
    return 0;
}