在朴素中透着一点新意的状压DP
一个很暴力的思路是枚举位置，状态和硬币，每次二分出向前最多能买到哪里，复杂度爆炸($O(2^knklog$ $n)$)
考虑优化，不妨先预处理一下$goal[i][j]$表示每个硬币$i$在每个位置$j$最多向前能买到哪里，但是这样还是很爆炸，所以我们找来了一个不同寻常的dp状态
我们设$dp[s]$表示在$s$状态下最远能到达哪里，于是有了一个清奇的转移方程$dp[s|(1<<coin)]=max(dp[s|(1<<coin)],goal[coin][dp[s]]$，这样就可以$O(2^kk)$转移啦
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int K=,N=;
long long val[K],goal[N][K];
long long pri[N],fsum[N],dp[<<];
long long k,n,all,ans=-;
int s(int x)
{
return <<(x-);
}
int main ()
{
scanf("%lld%lld",&k,&n),all=(<<k)-;
for(int i=;i<=k;i++)
scanf("%lld",&val[i]);
for(int i=;i<=n;i++)
scanf("%d",&pri[i]),fsum[i]=fsum[i-]+pri[i];
for(int i=;i<n;i++)
for(int j=;j<=k;j++)
{
int l=i+,r=n,ed=i;
while(l<=r)
{
int mid=(l+r)/;
if(fsum[mid]-fsum[i]>val[j]) r=mid-;
else l=mid+,ed=mid;
}
goal[i][j]=ed;
}
for(int i=all;i;i--)
for(int j=;j<=k;j++)
if(i&s(j)) dp[i^s(j)]=max(dp[i^s(j)],goal[dp[i]][j]);
for(int i=;i<=all;i++)
if(dp[i]==n)
{
long long cnt=;
for(int j=;j<=k;j++)
if(i&s(j)) cnt+=val[j];
ans=max(ans,cnt);
}
printf("%lld",ans);
return ;
}