CF467C George and Job 题解

· · 题解

这道题给我的第一反应就是，要用前缀和。毕竟要求的是一段，前缀和就能发挥出它的优势。

什么是前缀和

先来聊聊什么是前缀和，其实很简单，根据字面意思可知，就是前几个数的和。

再来讲讲它的运用。

给你 n 个数，让你求连续 m 个数的和的最大值。如果不用前缀和的话，就是 O(nm) 的算法，可世间总不那么美好，总有一些恶心出题人会出一些比较大的数据，这时，我们就不得不用前缀和了。前缀和的思想很简单，就是大段减小段等于剩下那段，这样，就华丽的转身到了 O(n) 的算法。

回入正题，本题除了要用前缀和，还得用 dp 这不废话，标签上都写着，但本蒟蒻并不推荐还没做就看标签，毕竟考场上可不会有标签给你看。这题动态转移方程其实很好写，前 i 组数列在前 j 个数的最大值其实就相当于前 i - 1个数， n - m 个数在加上这一段的和。整理亿下，就是 f[i][j] = f[i - 1][j - k] + sum[j] - sum[j - k] ，f[i - 1][j - k] 这玩意儿就用 g[j - m] ，替代。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long//千年OI一场空，不开longlong见祖宗 
const int maxn = 1e6 + 10;
int n, m, k, ans;
int a[maxn], sum[maxn], f[5010][5010], g[maxn];
signed main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for(int i = 1; i <= k; ++i){
        for(int j = m; j <= n; ++j)
            f[i][j] = g[j - m] + sum[j] - sum[j - m];//因为下面g[j - m]已经取过前面的max了，所以这里不用max; 
        for(int j = 1; j <= n; ++j)
            g[j] = 0;
        for(int j = 1; j <= n; ++j)
            g[j] = max(g[j - 1], f[i][j]);
    }
    for(int i = m; i <= n; ++i)//以防万一 
        ans = max(ans, f[k][i]);
    cout << ans << '\n';
    return 0;
}