一道很妙，也挺有技巧的状压dp题。
我们从k入手，k的范围很小，且本题是按顺序购买的。
接下来是本题的核心：dp[i]是状态为i时，最多能买多少物品数
接下来是dp的状态转移：
我们知道 i 的状态有那些为1，我们把第 j 个钱放在最后花，然后已经知道了 dp[ i^(1<<j) ] 的最优解，便可用这个推向dp[i]
if( i&(1<<j) ) dp[i]=max(dp[i],calc(a[j]) ) 其中calc(a[j])表示从(dp[ i^(1<<j) ]+1)开始,用a[j]的钱最多买到了，这部分用二分来处理
然后便是统计答案，没什么好说的
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second const int N=18; const int M=1e5+10; //const int inf=0x3f3f3f3f; //const ll INF=0x3ffffffffffff; int T,n,m,b[M],dp[1<<N]; ll a[N],sum[M]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); n=read(),m=read(); for(int i=0;i<n;i++) scanf("%lld",&a[i]); for(int i=1;i<=m;i++) b[i]=read(),sum[i]=sum[i-1]+b[i]; for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) { if(!(i&(1<<j))) continue; int L=dp[i^(1<<j)]; int R=upper_bound(sum+1,sum+m+1,a[j]+sum[L])-sum-1; dp[i]=max(dp[i],R); } } ll ans=-1; for(int i=0;i<(1<<n);i++) { if(dp[i]==m) { ll res=0; for(int j=0;j<n;j++) if(!(i&(1<<j))) res+=a[j]; ans=max(ans,res); } } printf("%lld",ans); return 0; }