题解 P3092 【[USACO13NOV]No Change G】

· · 题解

其实这题代码真的很短

我们来换一种dp方式（当然这种dp方式题解里好像有，但是讲的不太详细，于是我来补充一下）

仍然是状压dp

令 f[st] 为当前硬币使用状态为 st 时多买到几号物品

我们考虑 f[i] 能转移到那些地方

显然，f[i]\rightarrow f[j] 当 j=i+2^k 且 2^k\&i=0 的时候可以转移

其中，\& 表示按位与运算

接下来，考虑转移多少

设当前转移使用的硬币是第 k 个硬币，价值为 w_k

那么，我们可以写出转移方程：f[i\ xor \ (2^k)]=\max(f[i\ xor\ (2^k)],p) 其中 p 为满足 \sum_{i=f[i]}^{p}val_i\leq w_k 的最大值

注：xor 为按位异或运算，val_i 为 i 商品的价值

接下来，我们用前缀和优化，发现还可以用二分查找找到这个 p 于是这题就作完啦

时间复杂度：O(2^kk\log n)

附上我简短的代码：

#include<bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,K,ans;
int sum[MAXN],mon[MAXN];
int f[1<<17];
int find(int l,int r,int s)//二分查找
{
    int now=sum[l],ret=l;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(sum[mid]-now<=s)ret=mid,l=mid+1;
        else r=mid-1;
    }
    return ret;
}
int fl=0;
int main()
{
    scanf("%d%d",&K,&n);
    for(int i=1;i<=K;i++)scanf("%d",&mon[i]);
    for(int i=1;i<=n;i++)scanf("%d",&sum[i]),sum[i]+=sum[i-1];
    int max_state=(1<<K)-1;
    for(int i=0;i<=max_state;i++)
    {
        for(int j=1;j<=K;j++)
        {
            if((i>>j-1)&1)continue;
            f[i|(1<<j-1)]=max(f[i|(1<<j-1)],find(f[i],n,mon[j]));//转移
        }
        if(f[i]==n)
        {
            int a=i,cnt=0;fl=1;
            for(int j=1;j<=K;j++)
            {
                if((i>>j-1)&1)continue;
                cnt+=mon[j];
            }
            ans=max(ans,cnt);
        }
    }
    if(!fl)printf("-1");
    else printf("%d",ans);
    return 0;
}

还有一个转移顺序问题，我想了好长时间，但是后来想想是我考虑多了。

我们考虑状态 st，能转移到它的一定是它的一个子集 st' 所以，很明显 st>st' 于是当我们从小到大枚举时，枚举到 st 时 st 一定被转移完了，也就是到达最终状态了，我们就可以放心的用状态 st 来转移其他的状态啦~