题目大意
给定N个位置，每个位置i都有一个value[i]值，从中选择若干个位置，使得连续的M个位置中的被选中的位置数目不超过Q，求出所有选择方案中value和最大的方案，输出其最大value和。
分析
1、可以采用枚举的方式，枚举出所有的选择可能情况，每次枚举成功后，更新全局变量最大值即可。时间复杂度O(2^N).当然会超时...
//index为dfs搜索到的位置，num_in_last_M 为前M个位置中有多少个已经被选中，
//total_value为搜索到当前位置时，总的value
void dfs(int index, int num_in_last_M, int total_value){
if (index == N){ //递归出口
max_value = max_value > total_value ? max_value : total_value;
return;
}
//当前index处的位置不选中
dfs(index + , num_in_last_M, total_value);
if (index < M){
if (num_in_last_M < Q){
used[index] = true; //used[i] 用于表示位置i是否被选中
dfs(index + , num_in_last_M + , total_value + wastes[index]);
}
}
else if(num_in_last_M - used[index - M] < Q){
used[index] = true;
dfs(index + , num_in_last_M - used[index - M] + , total_value + wastes[index]);
}
//回溯！！！
used[index] = false;
}
2、采用动态规划的方式
dp[i][j] 表示前i个位置中，位置(i-M+1, i-M+2, ... i)构成的选中情况的二进制表示（0表示未选中，1表示选中）为j时，可以得到的最大值。
问题满足最优化子结构：从dp[i-1][k] 过渡到dp[i][j]时，如果dp[i][j]取得了最大值，那么dp[i-1][k]也一定为状态(i-1, k)的最大值； 问题无后效性：从dp[i-1][k]推演到dp[i][j]时，不关心 状态(i-1,k)是如何得到的，只关心最后的结果。
在求完dp数组之后，如果想要获得最后的结果，需要遍历dp[N]K来获得所有情况的最大值。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<string>
#include<string.h>
#include<stdio.h>
#include<functional> using namespace std; int dp[1005][1030];
int waste[1005];
int main(){
int N, Q, M;
scanf("%d %d %d", &N, &M, &Q);
for (int i = 0; i < N; i++){
scanf("%d", &waste[i]);
}
for (int i = 0; i < N; i++){
for (int j = 0; j < (1 << min(i + 1, M)); j++){
int k = 0;
int jj = j;
while (jj){
k += (jj & 1);
jj >>= 1;
}
if (k > Q)
dp[i][j] = 0;
else{
jj = j >> 1;
dp[i][j] = max(dp[i][j], i > 0 ? dp[i - 1][jj] : 0);
jj |= (1 << min(i, M-1));
dp[i][j] = max(dp[i][j], i > 0 ? dp[i - 1][jj] : 0);
if (j & 1)
dp[i][j] += waste[i];
}
}
}
int result = 0;
for (int x = 0; x < (1 << min(M, N)); x++){
result = max(result, dp[N - 1][x]);
}
printf("%d\n", result);
return 0;
}