当前位置：首页 > news >正文

2018.10.23-dtoi-1770不设找零No Change (nochange)

news 来源：原创 2024/5/1 9:13:38

题目描述：

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

请计算FJ完成N件物品的购物后，所能剩下的最大钱数。如果他无法买到所有物品，输出-1。

输入：

第1行：两个整数K，N；

第2～K+1行：每行为一个硬币面值；

第K+2～N+K+1行：这N行为FJ所要购买的N件物品的价值。

输出：

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

算法标签：状压dp

思路：

看到硬币种类只有16个大概能想到状态压缩，尽管如此之后的dp还是挺妙的，每次对当前剩余的钱硬币，选择则一枚用来看至多能买到哪，好像将不清楚，看看代码能懂。

（一开始没看到一次只能用一个硬币买，哭了）

以下代码：

#include<bits/stdc++.h>
#define N 100005
#define M 66000
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
int k,n,sum[N],c[17],b[17],f[M];
int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;return f*x;}
int main()
{
    k=read();n=read();
    for(int i=1;i<=k;i++)c[i]=read();
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+read();
    b[1]=1;for(int i=2;i<=k;i++)b[i]=b[i-1]<<1;
    int maxn=(1<<k)-1;
    for(int i=0;i<=maxn;i++)
        for(int j=1;j<=k;j++)
            if(i&b[j]){
                int tmp=f[i^b[j]];
                tmp=upper_bound(sum+1,sum+n+1,sum[tmp]+c[j])-sum;
                f[i]=max(tmp-1,f[i]);
            }
    int ans=-1;
    for(int i=0;i<=maxn;i++)
        if(f[i]==n){
            int tmp=0;
            for(int j=1;j<=k;j++)if(!(b[j]&i))tmp+=c[j];
            ans=max(ans,tmp);
        }
    printf("%d\n",ans);
    return 0;
}