---恢复内容开始---
【题目描述】 在 L 的书架上，有 N 本精彩绝伦的书籍，每本书价值不菲。 M 是一个书籍爱好者，他对 L 的书籍早就垂涎三尺。最后他忍受不了诱惑，觉得去偷 L 的 书，为了迅速完成这件事，同时他不希望 L 很快发现书籍少了，他决定偷书时，对于任意 连续的 k 本书，他最多选 B 本，最少选 A 本。现在他想知道怎么选出来的书本最后使得偷 的书籍的价值和，与剩下的书籍价值和，差值最大。
【数据范围】 n<=1000,0<=a<=b<=k<=10 k <= n 所有书籍的价值的绝对值<=10^9
注意到a,b,k<=10，很容易想到状压dp
题目是要求每一段连续的k都满足要求，首先明确，我们选出来的书籍肯定是越大越好。
设dp[i][state]表示前i本书 最后k本书状态为state的最大值
状态转移分为两种情况
1.如果当前状态s最后一位是1 也就是要买最后一本书 dp[i][s]=max(dp[i-1][s>>1]+val[i],dp[i-1][s>>1|(1<<(k-1))]+val[i])
2.如果最后一位是0 即不买 dp[i][s]=max(dp[i-1][s>>1],dp[i-1][s>>1|(1<<(k-1))])
注意还要check一下s>>1 s>>1|(1<<(k-1))两个状态是否合法
参考代码
//dp[i][s] 前i个人 k个人状态为s的最优解 #include<bits/stdc++.h> #define N 1005 #define ll long long using namespace std; int n,k,a,b,maxs; ll sum; ll dp[N][1025]; int nums[1024],val[N]; void init() { for(int s=0;s<1024;s++) { int temp=s,num=0; while(temp) { if(temp&1) num++; temp>>=1; } nums[s]=num; } } bool check(int state) { return (nums[state]>=a&&nums[state]<=b); } int main() { cin>>n>>k>>a>>b; for(int i=1;i<=n;i++){ cin>>val[i]; sum+=val[i]; } init(); for(int i=0;i<(1<<k);i++) //前k个数 { for(int j=0;j<k;j++) if(i&(1<<j)) dp[k][i]+=val[k-j]; //初始化前k个数 } } for(int i=k+1;i<=n;i++) { for(int s=0;s<(1<<k);s++) { if(!check(s)) continue; int t1=s>>1; if(s&1)//要选书 { int t2=t1|(1<<(k-1)); if(check(t2)) dp[i][s]=dp[i-1][t2]+val[i]; if(check(t1)) dp[i][s]=max(dp[i][s],dp[i-1][t1]+val[i]); } else { int t2=t1|(1<<(k-1)); if(check(t2)) dp[i][s]=dp[i-1][t2]; if(check(t1)) dp[i][s]=max(dp[i][s],dp[i-1][t1]); } } } ll ans=LLONG_MIN; for(int s=0;s<(1<<k);s++) { if(check(s)) ans=max(ans,dp[n][s]); } cout<<ans-sum+ans; return 0; }