状态压缩 写了两个半小时 太菜了
题目链接 https://hihocoder.com/contest/hiho8/problem/1
#include <bits/stdc++.h>
using namespace std; const int N = ;
const int MAXN = <<;
int n, m, q, w[MAXN]; // 存取到达i时候, 前面m-1个的状态
int dp[][MAXN]; int Count(int x)
{
int cnt = ;
while(x) {
cnt += x%;
x/=;
}
return cnt;
} void print(int tmp)
{
int mx = ;
for(int st=; st<(<<m); st++) {
mx = max(mx, dp[tmp][st]);
}
cout << mx <<endl;
} void printAll()
{
for(int i=;i<n;i++) {
print(i);
}
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d %d %d", &n, &m, &q);
for(int i=; i<n; i++) {
scanf("%d", &w[i]);
}
// 第0个选就是0 第0个不选就是 w[0]
dp[][] = ; dp[][] = w[];
for(int i=; i<n; i++) {
if(i < m) {
// 前m个很好转移,就是 dp[i][st] = dp[i-1][st];
// 记录前i-1个的状态的最优值 如果当前i能插入 就更新最优值
for(int st=; st<(<<(i)); st++) {
dp[i][st] = max(dp[i][st], dp[i-][st]);
if(Count(st) < q && (&(st>>i))== ) {
dp[i][st+(<<i)] = max(dp[i][st+(<<i)], dp[i][st] + w[i]);
}
}
}
else {
// 之前的记录的是 [i-m+1, i]
// 现在需要更新成 [i-m+2, i+1]
// 所以整体 i-m+1位不需要了 就是 dp[i][st>>1] = dp[i-1][st]
for(int st=; st < (<<m); st++) {
dp[i][st>>] = max(dp[i][st>>], dp[i-][st]);
} // 由于此时i>=m了 保证之前肯定有m-1个状态, 所以前m-1个状态 分别在[0, m-2]之间
// 因而此时的i 应该放在 m-1 位, 然后可以插入i, 就更新最优值
for(int st=; st<(<<m); st++) {
//int k = i%m + 1;
int k = m-;
if(Count(st) < q && ( & (st >> k))==) {
dp[i][st+(<<k)] = max(dp[i][st+(<<k)], dp[i][st] + w[i]);
}
}
}
}
//printAll();
print(n-);
return ;
}