洛谷P3092 状压dp

题意：

有一个人有$n$枚硬币$(n\le 16)$，面值为$a_i$，有$m$个商品，价格为$t_i$，这个人需要从$1$到$m$的顺序购买完所有商品，他的购买方式如下，他将商品放入购物车时不需要立即付款，它可以在任意时候付款，付款的总额为除之前购买完的商品之外的列入清单的商品。问购买完毕后，剩余的硬币最大总额是多少？如果不能完成购买，输出$-1$

方法：

$n\le 16$，想到状态压缩$dp$，现在问题在如何设置状态，显然硬币这一维度是必须的

假如设$dp[i][s]$为买完前$i$个商品，硬币状态为$s$是否有可能，那么枚举的时间复杂度就是$O(m{2}^n)$，因此买完前几个这个应该是不能被算入一个维度的，但又是必须，所以不妨考虑这样设，$dp[s]$，所剩硬币状态为$s$，能够买到最远的商品是第$dp[s]$个，这样子我们只需要站在用之前的硬币买到最远的地方，枚举下一次使用的硬币，即可更新$dp[s^{\prime }]$

那么当前状态为$s$，我们枚举一枚没有使用过的硬币，假设这枚硬币是第$i$枚，那么我们就可以更新$dp[s|(1<<(i-1))]$，每次使用硬币应该是买的越多越好，所以，$dp[s|(1<<(i-1))]$应该是从$dp[s]+1$开始买，用$val[i]$的硬币最远能卖到哪里，这个过程可以二分，在$[dp[s]+1,m]$的前缀和上二分，找第一个大于等于$val[i]$的位置，这个区间的前缀和是全局的前缀和减去$sum[dp[s]]$，那么即在$[dp[s]+1,m]$上找第一个大于等于$val[i]+sum[dp[s]]$的位置，这个位置权值如果大于$val[i]+sum[dp[s]]$，那么能买到的就是前面一个位置的商品，否则就是当前找到的位置

#include
using ll=long long;
using namespace std;

int dp[100005],f[100005],ans=-1;
int n,m,val[20],t[100005],sum[100005];

int getleft(int s)
{
    int ret=0;
    for(int i=1;i<=n;i++)
        if((s>>(i-1)&1)==0) ret+=val[i];
    return ret;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&t[i]);
        sum[i]=sum[i-1]+t[i];
    }
    //dp[s]->我们花费了一些硬币，最远买到了dp[s]，f[s]是硬币转态为s时的最大剩余钱
    for(int s=0;s<(1<<n)-1;s++)//1为用了
    {
        for(int i=1;i<=n;i++)
        {
            if(s>>(i-1)&1) continue;
            int pos=lower_bound(sum+dp[s]+1,sum+1+m,val[i]+sum[dp[s]])-sum;
            if(sum[pos]!=val[i]+sum[dp[s]]) pos--;
            if(dp[s|(1<<(i-1))]<pos) dp[s|(1<<(i-1))]=pos;
            if(dp[s|(1<<(i-1))]==m) ans=max(ans,getleft(s|(1<<(i-1)))); 
        }
    }
    cout<<ans;
    return 0;
}