在朴素中透着一点新意的状压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)$转移啦
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int K=17,N=100005; 6 long long val[K],goal[N][K]; 7 long long pri[N],fsum[N],dp[1<<16]; 8 long long k,n,all,ans=-1; 9 int s(int x) 10 { 11 return 1<<(x-1); 12 } 13 int main () 14 { 15 scanf("%lld%lld",&k,&n),all=(1<<k)-1; 16 for(int i=1;i<=k;i++) 17 scanf("%lld",&val[i]); 18 for(int i=1;i<=n;i++) 19 scanf("%d",&pri[i]),fsum[i]=fsum[i-1]+pri[i]; 20 for(int i=0;i<n;i++) 21 for(int j=1;j<=k;j++) 22 { 23 int l=i+1,r=n,ed=i; 24 while(l<=r) 25 { 26 int mid=(l+r)/2; 27 if(fsum[mid]-fsum[i]>val[j]) r=mid-1; 28 else l=mid+1,ed=mid; 29 } 30 goal[i][j]=ed; 31 } 32 for(int i=all;i;i--) 33 for(int j=1;j<=k;j++) 34 if(i&s(j)) dp[i^s(j)]=max(dp[i^s(j)],goal[dp[i]][j]); 35 for(int i=0;i<=all;i++) 36 if(dp[i]==n) 37 { 38 long long cnt=0; 39 for(int j=1;j<=k;j++) 40 if(i&s(j)) cnt+=val[j]; 41 ans=max(ans,cnt); 42 } 43 printf("%lld",ans); 44 return 0; 45 }