[USACO13NOV]没有找零No Change [TPLY]

[USACO13NOV]没有找零No Change

题目链接 https://www.luogu.org/problemnew/show/3092

做题背景

FJ不是一个合格的消费者，不知法懂法用法，不会拿起法律的武器维护消费者权益

做法

本题涉及的知识点：状态压缩，动态规划，二分答案。

注意物品是依次购买

首先是状态压缩：

压什么？我们注意到k<=16,那么就是压硬币使用集合。

然后是动态规划：

怎么设状态?设dp[i]表示我们选硬币集合i（状压）从一号物品开始最多能买的物品数。

怎么转移？从0开始枚举每一个可能的硬币集合i（状压）

找到每一个存在于使用集合i中的硬币

（例如在集合11001中1，2，5是存在于集合i中的）

然后从不包含该硬币的集合中转移过来

（即11001从01001,10001,11000中转移过来）

再是二分答案：哪里需要二分答案？在转移过程中.我们需要找到利用硬币最多能买到的物品数，枚举太耗时间，前缀和二分答案就可以加快速度了。

几点注意：

转移开long long

位运算优先级有点头疼，能打括号打括号

Ans设为-1，不能设为0因为可能存在正好一点不剩的最优解

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define RG register

#define rg register int

#define rc register char

#define ll long long

#define il inline

#define INF 2147483647

#define SZ 100001

using namespace std;

il int gi()

{

	rg x=0,o=0;rc ch=getchar();

	while(ch!='-'&&(ch<'0'||'9'<ch))ch=getchar();

	if(ch=='-') o=1,ch=getchar();

	while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return o?-x:x;

}

int k,n;

ll tot,Ans,a[SZ],sum[SZ],dp[65537],c[17];

// 查询一个数二进制中1的个数

il ll num(rg x)

{

	RG ll cnt=0;

	for(rg i=0;i<k;++i)

	 if((x>>i)&1)

	  cnt+=c[i+1];

	return cnt;

}

//手写upperbound函数

il int Upper(ll *array,int size,ll key)

{

	rg hd=1,len=size;

	while(len>0)

	{

		rg mid=hd+(len>>1);

		if(array[mid]>key) len>>=1;

		else hd=mid+1,len=len-(len>>1)-1;

	}

	return hd;

}

// upper_bound

int main()

{

	k=gi(),n=gi();

	for(rg i=1;i<=k;++i) c[i]=gi(),tot+=c[i];

	for(rg i=1;i<=n;++i) a[i]=gi(),sum[i]=sum[i-1]+a[i];

	for(rg i=0;i<=(1<<k)-1;++i)

	 for(rg j=0;j<k;++j)

	  if((i>>j)&1)

	  {

	      ll tmp=(i^(1<<j));

	      tmp=Upper(sum,n,sum[dp[tmp]]+c[j+1]);

	      dp[i]=max(dp[i],tmp-1);

	  }

	Ans=-1;

	for(rg i=0;i<=(1<<k)-1;++i)

	 if(dp[i]==n)

	  Ans=max(Ans,tot-num(i));

	printf("%lld",Ans);

	return 0;

}