题解 P3092 【[USACO13NOV]没有找零No Change】

· · 题解

楼下是Pascal，我来发c++；

这是我做的第一题状压，所以写了很详细的过程。

都在代码后面~

/*Miroerwf_Q*/

#include<iostream>
//#include<cstdio>
//#include<cstring>
#include<cmath>
#include<algorithm>
//#include<queue>
//#define LL long long
using namespace std;
int m,n,a[100001];/*物品数组*/int sum[100001];/*前缀和*/int c[17]/*硬币*/;
int b[17];/*每个硬币的状态*/int f[(1<<16)+10];/*在某个状态下购买的物品数*/
int maxx;/*用二进制表示状态时的最大值*/int ans=-1;/*结果*/int tot;/*总钱数*/
int main()
{
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>c[i];
        tot+=c[i];/*记录总钱数*/
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];/*记录前缀和*/
    }
    b[1]=1;
    for(int i=2;i<=m;i++){
        b[i]=b[i-1]<<1;/*二进制(十进制)：b[1]=1(1),b[2]=10(2),b[3]=100(4),b[4]=1000(8),*/
    }        /*b[5]=10000(16),------,b[m]=100---00(2的m-1次方),表示只选第i个硬币的状态。*/
    maxx=(1<<m)-1;
    for(int i=0;i<=maxx;i++)
        for(int j=1;j<=m;j++)
            if((i&b[j])){/*如果i&b[j]不等于零,也就是选第j个硬币.*/
                int tmp=f[i^b[j]];/* i^b[j]是不选第j个硬币的状态,tmp即是不用第j个硬币可以购买的物品数.*/
                tmp=upper_bound(sum+1,sum+n+1,sum[tmp]+c[j])-sum;/*upper_bound是c++STL库的函数,解释在上面.*/
                /*            此时的tmp就是第一个大于(额...是前缀和大于)sum[tmp](这是原先买物品花的钱)+c[j](这是这个硬币的面值)的物品的位置.*/
                /*         那么tmp之前的物品都买过了(不包括他自己).*/
                f[i]=max(f[i],tmp-1);/*tmp-1就是已经买的物品,拿来更新f[i];*/
            }
    for(int i=0;i<=maxx;i++)/*从最小状态到最大状态(是用来表示状态的数最小(大),不是状态最小(大),2333)时,有多种购买方法,枚举一遍进行处理.*/
        if(f[i]==n){/*状态为i时买了全部的n个物品,也就是此状态是一种购买方案.*/
            int cnt=0;/*记录用掉的总钱数*/
            for(int j=1;j<=m;j++)/*枚举硬币，看看哪一个硬币使用了.*/
                if(i&b[j])/*   i&b[j]不为零,即j这个硬币使用了.*/
                    cnt+=c[j];
        ans=max(ans,tot-cnt);/*求最多剩余的钱.*/
        }
        if(ans<0)/*判断是不是买不起,但为什么不直接等于零呢?,因为Fj可能正好买完所有物品二没硬币剩余~(Ovo)*/
        cout<<-1;
    else
        cout<<ans;
    return 0;
}