[HC - 1044] 状态压缩一

发表于 | 更新于 | 分类于 ， ，
本文字数： 13k

链接

\(\text{hihoCoder - 1044 状态压缩一}\)

题意

  火车上有\(n\)个座位排成一排，第\(i\)个座位上有数目\(w[i]\)的垃圾，你需要尽可能多的清扫这些垃圾，然而在连续\(m\)个座位上，你最多只能选取\(q\)个位置进行清扫，不然会让乘客不愉快，现在问你最多可以清扫多少数目的垃圾；

  输入格式：输入包含一组样例，第一行三个数\(n,m,q\)，第二行\(n\)个整数，第\(i\)个为\(w[i]\);

  数据范围：\(N\leq 1000,2\leq M\leq 10,1\leq q\leq m,w[i]\leq 100\).

  输出格式：输出一行代表最多可以清扫的垃圾数目；

分析

  如果我们考虑每个位置的选与不选，那么最多可能有\(2^1000\)种状态，显然这种想法不现实，我们发现，如果当前位置\(i\)的前\(m-1\)个位置中已经选了\(q\)个了(即在\([i-m+1,i-1]\)中选\(q\)个)，这种状态为\(j\)，那么显然当前位置一定不能选，所以当前位置的最大值等于，在第\(i-1\)个位置，\([i-m+1,i-1]\)中选了\(q\)个，而第\(i-m\)这个位置一定不选(对于\(i-1\)来说，需要在\([i-m,i-1]\)中选\(q\)个)，这时候的最大值，同理当第\(i\)个位置选的时候，考虑它的状态可以从\(i-1\)的什么状态转移过来即可。

  第\(i\)个座位为阶段，\(i\)之前包括\(i\)个\(m\)个选若干个为状态。

  首先预处理一下，\(m\)个连续座位里选小于\(q\)个座位的状态，具体细节见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 1000005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

int n, m, q, w[1005], f[1005][1 << 12], mark[1 << 12];
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    for (int i = 0; i < 1 << m; i++) {
        int cnt = 0;
        for (int j = 0; j < m; j++)
            if (i >> j & 1) cnt++;
        mark[i] = cnt;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 1 << m; j++) { 
            if (mark[j] <= q) {
                if (j & 1)  f[i][j] = max(f[i - 1][j >> 1], f[i - 1][(j >> 1) + (1 << (m - 1))]) + w[i];
                else {
                    if (mark[j] == q) f[i][j] = f[i - 1][j >> 1];
                    else if (mark[j] < q)
                        f[i][j] = max(f[i - 1][j >> 1], f[i - 1][(j >> 1) + (1 << (m - 1))]);
                }
            }
        }
    int ans = -1;
    for (int i = 0; i < 1 << m; i++)
        if (mark[i] <= q) ans = max(f[n][i], ans);
    cout << ans << endl;
}