Thông tin
https://oj.clue.edu.vn/problem/dhbb26seq https://oj.clue.edu.vn/problem/tqhsg26d -> nâng lên n = 2e5 https://oj.clue.edu.vn/problem/dntst24varr https://oj.clue.edu.vn/problem/hnhsg25e https://oj.clue.edu.vn/problem/hsgso26recurio https://oj.clue.edu.vn/problem/voi26pine 50b30 50b35 50b40 50b45 50b50 50b55 50b60
include <bits/stdc++.h>
using namespace std;
define ll long long
const ll N = 2e5 + 5;
ll n,k,t[N]; namespace sub1 { ll f[5005][5005],res = 1e18; void solve() { for(ll i = 1; i <= n; i ++) { for(ll j = 1; j <= n; j++) { f[i][j] = 1e18; } } for(ll i =1 ; i <= n; i ++) { for(ll j = 1 ; j <= i; j++) { ll chiphi = t[i] + 1 - t[j] + 1; for(ll x = 0; x <= k - 1; x ++) { if(f[j - 1][x + 1] != 1e18) f[i][x] = min(f[i][x],f[j - 1][x + 1] + chiphi); } } } fl(i,1,k) { res = min(res,f[n][i]); } cout << res; } } namespace sub2 { ll f[5005][5005],g[5005],res = 1e18; void solve() { for(ll i = 1; i <= n; i ++) { for(ll j = 1; j <= k; j++) { f[i][j] = 1e18; } } for(ll i =1; i <= k; i++) { g[i] = 1e18; f[0][i] = 1e18; } for(ll i =1 ; i <= n; i++) { for(ll x = 1; x <= k; x++) { g[x] = min(g[x],f[i - 1][x] - t[i]); } for(ll x = 0; x <= k - 1; x ++) { if(g[x + 1] != 1e18) { f[i][x] = min(f[i][x],g[x + 1] + t[i] + 1); } } } for(ll i = 0; i<= k; i++) { res = min(res,f[n][i]); } cout << res; } } main() { cin.tie(0)->syncwithstdio(0); cin >> n >> k; for(ll i = 1; i <= n; i++) { cin >> t[i]; } if(n <= 400) sub2::solve(); else if(n <= 5000) sub3::solve(); }