在L的书架上，有 N本精彩绝伦的书籍，每本书价值不菲。
M 是一个书籍爱好者，他对 L 的书籍早就垂涎三尺。最后他忍受不了诱惑，觉得去偷 L 的书，为了迅速完成这件事，同时他不希望 L 很快发现书籍少了，他决定偷书时，对于任意连续的 k 本书，他最多选 B 本，最少选 A 本。现在他想知道怎么选出来的书本最后使得偷的书籍的价值和，与剩下的书籍价值和，差值最大。
第一行四个整数 n,k,a,b
一行 N 个整数表示每本书的价值
一个整数表示答案
2 1 0 1
2 -2
4
对于 20%：n<=10
对于另外 20%：a=0,b=k
对于 100%：n<=1000,0<=a<=b<=k<=10,所有书籍的价值的绝对值<=10^9
一看到k<=10，这么小的数据简直就是宣告这是一道状压DP的题，那么就定义一个数组dp[i][j]，其中i表示前i个，状态为j（包含第i个）的最大价值，易得对于每个合法dp[i][j]，均可从dp[i-1][j>>1]和dp[i-1][（j>>1）|（1<<k）]转移而来，所以先预处理出所有合法情况（即1的个数大于等于a而小于等于b），最后扫一遍dp[n][k]即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<queue> 7 #include<cmath> 8 using namespace std; 9 typedef long long LL; 10 const LL MAXN=1<<11; 11 const LL INF=0x3f3f3f3f; 12 13 LL dp[1001][MAXN]; 14 LL n,k,a,b; 15 LL val[1001]; 16 bool che[MAXN]; 17 18 LL Read() 19 { 20 LL i=0,f=1; 21 char c; 22 for(c=getchar();(c>‘9‘||c<‘0‘)&&c!=‘-‘;c=getchar()); 23 if(c==‘-‘) 24 f=-1,c=getchar(); 25 for(;c>=‘0‘&&c<=‘9‘;c=getchar()) 26 i=(i<<1)+(i<<3)+c-‘0‘; 27 return i*f; 28 } 29 30 void pre() 31 { 32 for(LL i=0;i<=MAXN;++i) 33 { 34 LL t=i; 35 LL cnt=0; 36 while(t) 37 { 38 if(t&1) 39 cnt++; 40 t>>=1; 41 } 42 if(cnt>=a&&cnt<=b) 43 che[i]=true; 44 } 45 } 46 47 int main() 48 { 49 memset(dp,INF,sizeof(dp)); 50 n=Read(),k=Read(),a=Read(),b=Read(); 51 LL ans=-dp[0][0],inf=dp[0][0]; 52 pre(); 53 LL tot=0; 54 for(LL i=1;i<=n;++i) 55 val[i]=Read(),tot+=val[i]; 56 for(LL j=0;j<(1<<k);++j) 57 dp[0][j]=0; 58 LL cs=1<<k; 59 for(LL i=1;i<=n;++i) 60 { 61 for(LL j=0;j<cs;++j) 62 { 63 if(che[j]) 64 { 65 if(dp[i-1][j>>1]!=inf&&dp[i-1][(j>>1)|(1<<(k-1))]!=inf) 66 { 67 if(j&1) 68 dp[i][j]=max(dp[i-1][j>>1],dp[i-1][(j>>1)|(1<<(k-1))])+val[i]; 69 else 70 dp[i][j]=max(dp[i-1][j>>1],dp[i-1][(j>>1)|(1<<(k-1))]); 71 } 72 else 73 { 74 dp[i][j]=min(dp[i-1][j>>1],dp[i-1][(j>>1)|(1<<(k-1))]); 75 if(dp[i][j]==inf) 76 continue; 77 if(j&1) 78 dp[i][j]+=val[i]; 79 } 80 } 81 } 82 } 83 for(LL i=0;i<cs;++i) 84 { 85 if(dp[n][i]==inf) 86 continue; 87 ans=max(ans,dp[n][i]); 88 } 89 cout<<ans*2-tot; 90 return 0; 91 }
原文：https://www.cnblogs.com/Ishtar/p/9736860.html