# Lời giải:
- Trước hết hãy bỏ qua giới hạn $m$ <= 1e5 thì nhận ra rằng đây là một bài quy hoạch động
- Gọi $dp[i][j]$ là giá trị lớn nhất có thể chọn $j$ phần tử từ $1 -> i$ và
kết thúc tại $i$.
- Ta có công thức truy hồi:
$dp[i][j] = max(dp[i][j], dp[z][j-1] + j.a[i])$
Với $i$ từ $1$ -> $n$ , $j$ từ $1$ -> $k$ và $z$ từ $i-m$ -> $i-1$
- Vậy là có thể giải quyết bài toán này nếu như bỏ qua giới hạn $m$ <= 1e5, giờ làm sao để giải
quyết giới hạn này?
- Nhận xét: Việc duyệt $z$ là để tìm ra $dp[z][j-1]$ lớn nhất trong đoạn độ dài $m$ kết thúc
tại $i-1$, vậy có cách nào để tìm ra phần tử lớn nhất trong một đoạn độ dài $m$
nhanh hơn không ?
- Đó chính là bài toán này: https://marisaoj.com/problem/336 (thay vì tìm phần tử nhỏ nhất, thì
dùng kĩ thuật trong bài để tìm phần tử lớn nhất).
- Độ phức tạp: $O( n.k.Log(m))$ .
# Code:
``` cpp
#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
#define Size(a) (int)a.size()
#define bit(mask, i) ((mask>>i)&1)
#define Mask(i) (1<<(i))
using namespace std;
const int Maxn = 1e5+5;
const int mod = 1e9+7;
const int inf32 = 2e9+5;
const long long inf64 = 2e18+7;
int n, m, k;
int a[Maxn];
ll dp[Maxn][205];
deque<int> p[Maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> k;
f1(i,1,n) cin >> a[i];
p[0].push_front(0);
ll ans = 0;
f1(i,1,n)
{
f1(j,1,min(k, i))
{
dp[i][j] = max(dp[i][j], dp[p[j-1].front()][j-1] + 1ll*j*a[i]);
ans = max(ans, dp[i][j]);
}
f1(j,1,min(k,i))
{
while(!p[j].empty() && dp[i][j] >= dp[p[j].back()][j]) p[j].pop_back();
p[j].push_back(i);
if (i-p[j].front()+1 > m) p[j].pop_front();
}
}
cout << ans;
return 0;
}
```
zxcvbnm0123toi
Created at
3 likes