题目大意

题意

分析

考虑 f[i][j]f[i][j] 以第 ii 个数结尾，选了 jj 个的最大价值

因为要每 kk 个至少要有一个元素被选择, 对于第 i 个 位置，是通过 [i−k,i−1][i-k,i-1] 转移来的

易写出转移方程

1
2
3
4
5
6
for(int i = 1;i <= n;i++)
    for(int j = 1; j <= x;j++){
        for(int t = max(0ll,i-k); t<= i-1;t++){
            f[i][j] = max(f[i][j],f[t][j-1]+a[i]);
        }
    }

在 [n−k+1,n][n-k+1,n] 中统计答案,时间复杂度为 0(n3)0(n^3)

考虑优化

观察上述式子发现 f[i][j]=max(f[i][j],f[t][j−1]+a[i]);f[i][j] = max(f[i][j],f[t][j-1]+a[i]); 在求的就是f[j−1][]f[j-1][]中长度为 kk 的最大值

这样可以利用单调队列进行优化

考虑到优化的正确性我们将f[i][j]f[i][j]的两维互换表示为以第 jj 个数结尾，选了 ii 个的最大价值

把查询和添加封装成两个函数

add(t,x)add(t,x) 把f[t][x]f[t][x]插入第 t 个 队列

mx(t)mx(t) 查询第 tt 个队列的最值

1
2
3
4
5
6
7
8
9
10
11
12
void add(int t,int x){
    if (!Q[t].empty() && i - Q[t].front() >= k)
        Q[t].pop_front();
    while (!Q[t].empty() && f[t][Q[t].back()] < f[t][x]) 
        Q[t].pop_back();
    Q[t].push_back(x); 
}
int mx(int t){
    if(!Q[t].size) return -inf;
    return f[t][Q[t].front()];
}

参考

这样可以 O(n2)O(n^2) 求出

1
2
3
4
for(int i = 1;i <= n;i++){
    for(int j = 1;j<=x;j++) f[j][i] = mx(j-1) + a[i];
    for(int j = 0;j<=x;j++) add(j,i);
}

Code

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
int f[2505][2505];
deque<int> Q[2505];

int n,k,x;
void add(int t,int x){
    if (!Q[t].empty() && i - Q[t].front() >= k)
        Q[t].pop_front();
    while (!Q[t].empty() && f[t][Q[t].back()] < f[t][x]) 
        Q[t].pop_back();
    Q[t].push_back(x); 
}
int mx(int t){
    if(!Q[t].size) return -inf;
    return f[t][Q[t].front()];
}

signed main()
{
    cin>>n>>k>>x;
    vector<int> a(n+1);
    for(int i = 1;i <= n;i++) cin >> a[i];

    for(int i = 0;i <= 2505;i++) for(int j = 0;j <= 2505;j++)  f[i][j] = -inf;
    f[0][0] = 0;
    add(0,0);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j<=x;j++) f[j][i] = mx(j-1) + a[i];
        for(int j = 0;j<=x;j++) add(j,i);
    }
    
    int res = -1;
    for(int i = n-k+1;i <= n;i++){
        res = max(res,f[i][x]);
    }
    cout << res << endl;

    return 0;
}