P3092 [USACO13NOV] No Change G 题解

状压

dp

练习题

注意到

k

很小，显然要枚举

k

的状态，但还不确定用什么枚举方式。题目所说一个硬币只能用一次且不找零，所以多个硬币组合起来表示没有意义。至于为什么不能直接贪，因为用大面值去买贵物不一定更优，所以有问题。

由错误的贪心看出了一个需要解决的问题，硬币使用顺序不同对答案产生了不同影响，加上

k

小，那就是经典的状压

dp

了

那自然是想到

dp

了，可以考虑枚举状态

i

每个硬币是否使用过。那我们发现了，状态已经表示了代价，不需要

dp

他。题目中要求顺序买完n个物品，所以

dp

值表示的自然是每个状态下最多能顺序买到哪个物品,这样

dp

转移就能解决硬币使用顺序的问题（每种顺序都经过最优化了）。

f_{i}:

硬币使用情况为

i

下，最多顺序买到哪个物品,并预处理

d_{i,j}

表示用硬币

j

从第

i+1

个物品开始买能买到哪个物品，复杂度

O(nk\log n)

，加了个二分。

转移：

{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;
}

P3092 [USACO13NOV] No Change G 题解

文章操作

相关推荐

评论

P3092 [USACO13NOV] No Change G 题解