AcWing 4378. 选取数对
原题链接
困难
作者:
只想白嫖
,
2022-03-21 17:23:36
,
所有人可见
,
阅读 166
详情看注释
时间复杂度
- 未优化 – O$O(n^3)$
- 优化 – $O(n^2)$
C++ 代码
/*
author: A Fei
solution:
状态表示:
f[i][j]: 第i个数作为第j个区间的右端点的所有方案
属性:Max
状态转移: f[i][j] = max(f[k][j - 1]) + s[i] - s[i - m];
k的范围为:(j - 1) * m ~ i - m.
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5010;
LL f[N][N], s[N];
int a[N];
int n, m, k;
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
memset(f, -0x3f, sizeof f);
for(int i = 1; i <= n; i ++) f[i][0] = 0; //数i作为第0个区间右端点的值为0
//未优化--三重循环:先枚举ai,枚举区间,找状态转移
// for(int i = m; i <= n; i ++)//枚举每个数
// {
// for(int j = 1; j <= k; j ++)//枚举每个数在的区间
// {
// LL maxv = 0;
// for(int y = (j - 1) * m; y <= i - m; y ++)
// maxv = max(maxv, f[y][j - 1]);
// f[i][j] = maxv + s[i] - s[i - m];
// }
// }
//优化:先枚举区间j
for(int j = 1; j <= k; j ++)
{
LL maxv = 0;
for(int i = j * m; i <= n; i ++)
{
maxv = max(maxv, f[i - m][j - 1]);//maxv存的即为:max(f[0 ~ i - m][j - 1]) -- 这样就省去计算f[i][j]的枚举了。
f[i][j] = maxv + s[i] - s[i - m];
}
}
LL res = 0;
for(int i = 1; i <= n; i ++) res = max(res, f[i][k]);
cout << res << endl;
return 0;
}