HihoCoder 1044 - 状态压缩 (状态压缩DP)
思路
$dp[i][s]$，表示前i个位置，按照s中的位置扫垃圾的最大值。
枚举状态。如果当前位置有扫，就加上权，不然就取第i-m个位置选不选的最大值。
代码
int w[MAXN];
int dp[MAXN][1<<10];
int main()
{
//ROP;
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < (1<<min(i, m)); j++)
{
if (__builtin_popcount(j) > q) continue;
if (~j & 1) dp[i][j] = max(dp[i-1][j>>1], dp[i-1][(j>>1) + (1<<m-1)]);
else dp[i][j] = max(dp[i-1][j>>1], dp[i-1][(j>>1) + (1<<m-1)]) + w[i];
}
}
int ans = 0;
for (int i = 0; i < (1<<min(m, n)); i++) ans = max(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}