LG3092 「USACO2013NOV」No Change 状压DP

问题描述

https://www.luogu.org/problem/P3092

题解

观察到 \(k \le 16\) ，自然想到对 \(k\) 状压。

设 \(opt[i]\) 代表使用硬币状况为 \(i\) 时，最多可以买到 \(opt[i]\) 个物品。

然后 \(opt[i]\) 在DP过程中二分求出。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

int n,k;
int mon[23],s[1000000],opt[1000000],ans=-1;
int cot[1000000];

int find(int x){
    int l=1,r=n,mid,res=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(s[mid]<=x){
            l=mid+1,res=mid;
        }
        else r=mid-1;
    }
    return res;
}

int main(){
    read(k);read(n);
    for(int i=0;i<k;i++) read(mon[i]);
    for(int i=1;i<=n;i++){
        read(cot[i]);s[i]=s[i-1]+cot[i];
    }
    for(int i=0;i<(1<<k);i++){
        for(int j=0;j<k;j++){
            int pos=(i&(1<<j));
            if(!pos) continue;
            opt[i]=max(opt[i],find(s[opt[i xor (1<<j)]]+mon[j]));
        }
    }
    int sum;
    for(int i=0;i<(1<<k);i++){
        if(opt[i]!=n) continue;
        sum=0;
        for(int j=0;j<k;j++){
            if(!(i&(1<<j))) sum+=mon[j]; 
        }
        ans=max(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
}