P3092 [USACO13NOV] No Change G 题解
yokai_ing
·
·
题解
状压dp练习题
注意到k很小，显然要枚举k的状态，但还不确定用什么枚举方式。题目所说一个硬币只能用一次且不找零，所以多个硬币组合起来表示没有意义。至于为什么不能直接贪，因为用大面值去买贵物不一定更优，所以有问题。
由错误的贪心看出了一个需要解决的问题，硬币使用顺序不同对答案产生了不同影响，加上k小，那就是经典的状压dp了
那自然是想到dp了，可以考虑枚举状态i每个硬币是否使用过。那我们发现了，状态已经表示了代价，不需要dp他。题目中要求 顺序 买完n个物品，所以dp值表示的自然是每个状态下最多能顺序买到哪个物品,这样dp转移就能解决硬币使用顺序的问题（每种顺序都经过最优化了）。
转移：$${f_{i}=\max_{j\in [0,k-1]\cap (2^j\& i) }{d_{f_{i\oplus2^j},j+1}}~};$$
代码（很丑）：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int K=20,N=100010;
ll ans=-1,sum[N],s;
int n,k,c[N],a[K],d[N][K],f[1<<K];
int find(int l,int r,int x)
{
int ans=0,bg=l;
while(l<=r){
int mid=(l+r)/2;
if(sum[mid]-sum[bg]<=x)
ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main(){
scanf("%d%d",&k,&n);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]),s+=a[i];
sort(a+1,a+1+k);
for(int j=1;j<=k;j++)
d[n][j]=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
sum[i]=sum[i-1]+c[i];
}
for(int i=0;i<n;i++)
for(int j=1;j<=k;j++)
d[i][j]=find(i,n,a[j]);
for(int i=0;i<(1<<k);i++)
{
ll nows=0;
for(int j=0;j<k;j++)
{
int b=(i>>j)&1;
if(b)f[i]=max(f[i],d[f[i^(1<<j)]][j+1]),nows+=a[j+1];
}
if(f[i]==n)ans=max(ans,s-nows);
}
printf("%lld\n",ans);
return 0;
}
```