bzoj 3312 No Change

题目大意：

到商场购物，他的钱包里有K个硬币

想按顺序买 N个物品，第i个物品需要花费c(i)块钱

在依次进行的购买N个物品的过程中，可以随时停下来付款，每次付款只用一个硬币

支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）

如果支付的硬币面值大于所需的费用，他不会得到任何找零

请计算出在购买完N个物品后，最多剩下多少钱

思路：

状压dp

设使用了状态为i的硬币最远能够达到哪个物品

转移的时候从 i 里扔掉每一个1来转移过来

最后看一眼哪些dp可以达到n 取一下状态的补集求一下和

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define inf 2139062143

 #define ll long long

 #define MAXN 100100

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int k,n,dp[<<],s[MAXN],ans,val[];

 int lowbit(ll x) {return x&(-x);}

 int main()

 {

     k=read(),n=read();int x,t;

     for(int i=;i<=k;i++) val[i]=read();

     for(int i=;i<=n;i++) s[i]=s[i-]+read();

     for(int i=;i<k;i++) dp[<<i]=upper_bound(s+,s+n+,val[i+])-s-;

     for(int i=;i<(<<k);i++)

     {

         if(i==lowbit(i)) continue;

         for(int t=i,r=i;r;r-=lowbit(r))

         {

             t-=lowbit(r);

             dp[i]=max(dp[i],(int)(upper_bound(s+dp[t]+,s+n+,s[dp[t]]+val[int(log2(lowbit(r)))+])-s-));

             t+=lowbit(r);

         }

     }

     ans=-;

     for(int i=;i<(<<k);i++)

     {

         if(dp[i]!=n) continue;t=;

         for(int j=((<<k)-)^i;j;j-=lowbit(j))

             t+=val[int(log2(lowbit(j)))+];

         ans=max(t,ans);

     }

     printf("%d",ans);

 }

巴特西

bzoj 3312 No Change

最新文章

热门文章