洛谷3092 [USACO13NOV]No Change

题意

用 $K$ 个硬币购买 $N$ 个物品。商店不设找零，可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。

$N\le 100000 \ , \ K\le 16$ 。

题解

看到 $K\le 16$ ，状压。

用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品；预处理出 $v[i][j]$ 表示硬币 $i$ ，从 $j$ 物品开始买，能买到哪个物品；枚举当前用的硬币 $j$ ，可以得到方程：

$$f[i]=\max f[i \ xor \ 2^{j-1} ]+cnt[j][f[i \ xor \ 2^{j-1} ]]+1$$

如果 $f[i] \geq N$ ，就可以更新答案了。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,ans=-1,s[100005],c[17],f[65536],v[17][100005];

signed main()
{
    m=read(); n=read();
    const int N=1<<m;
    for (int i=1;i<=m;i++) c[i]=read();
    for (int i=1;i<=n;i++) s[i]=s[i-1]+read();
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            int cur=s[j-1]+c[i];
            v[i][j]=upper_bound(s+1,s+n+1,cur)-s-j; //预处理
        }
    }
    memset(f,-0x3f,sizeof(f)); f[0]=0;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<m;j++)
        {
            if (!(i>>j&1)) continue;
            int k=i^(1<<j);
            f[i]=max(f[i],f[k]+v[j+1][f[k]+1]);
        }
        if (f[i]<n) continue;
        int cur=0; //统计当前答案
        for (int j=0;j<m;j++)
        {
            if (i>>j&1) continue;
            cur+=c[j+1];
        }
        ans=max(ans,cur); //更新答案
    }
    return !printf("%d",ans);
}