fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  4. #define watch(x) cout << (#x) << " is " << (x) << endl
  5. #define f(t) for(ll i=0;i<t;i++)
  6. #define ll long long int
  7. #define ld long double
  8. #define umpl unordered_map<ll,ll>
  9. #define vl vector<ll>
  10. #define vld vector<ld>
  11. #define vvl vector<vl>
  12. #define pb push_back
  13. #define pll pair<ll,ll>
  14. #define inf 1e18
  15. #define pcout(x,p) cout<<fixed<<setprecision(p)<<x
  16. #define all(a) a.begin(),a.end()
  17. #define endl "\n"
  18. const ll mod = 1e9 + 7;
  19. inline ll mul(ll a, ll b) { return (a * 1ll * b) % mod; }
  20. inline ll sub(ll a, ll b) { ll c = a - b; if (c < 0) c += mod; return c; }
  21. inline ll add(ll a, ll b) { ll c = a + b; if (c >= mod) c -= mod; return c; }
  22. inline ll max(ll a, ll b) {return a > b ? a : b;}
  23. inline ll min(ll a, ll b) {return a < b ? a : b;}
  24. inline ll ceil(ll a, ll b) {return (a % b == 0) ? (a / b) : (a / b + 1);}
  25.  
  26.  
  27. const ll maxn = 5001;
  28. ll more[maxn][maxn];
  29. vl dp_before, dp_curr;
  30. ll cost(ll i, ll j) {
  31.     return more[j][j] - more[i - 1][j] - more[j][i - 1] + more[i - 1][i - 1];
  32. }
  33. void compute(ll l, ll r, ll low, ll high) {
  34.     if (l > r)return;
  35.     ll mid = (l + r) / 2;
  36.     pll best = {inf, -1};
  37.     for (ll k = low; k <= min(mid, high); k++) {
  38.         best = min(best, {dp_before[k - 1] + cost(k, mid), k});
  39.     }
  40.     dp_curr[mid] = best.first;
  41.     ll now = best.second;
  42.     compute(l, mid - 1, low, now);
  43.     compute(mid + 1, r, now, high);
  44. }
  45.  
  46. int main() {
  47.     fio;
  48.     ll t; cin >> t;
  49.     while (t--) {
  50.         ll n, k; cin >> n >> k;
  51.         vl a(n + 1);
  52.         for (ll i = 1; i <= n; i++)cin >> a[i];
  53.         memset(more, 0, sizeof(more));
  54.         for (int i = 1; i <= n; i++) {
  55.             for (int j = 1; j <= i; j++) {
  56.                 if (a[j] > a[i]) {
  57.                     more[i][j] = a[j];
  58.                 }
  59.             }
  60.         }
  61.         for (int i = 1; i <= n; i++) {
  62.             for (int j = 1; j <= n; j++) {
  63.                 more[i][j] = more[i - 1][j] + more[i][j - 1] - more[i - 1][j - 1] + more[i][j];
  64.             }
  65.         }
  66.         dp_before.resize(n + 1), dp_curr.resize(n + 1);
  67.         for (int i = 1; i <= n; i++) {
  68.             dp_before[i] = cost(1, i);
  69.         }
  70.         for (ll i = 2; i <= k; i++) {
  71.             compute(i, n, i, n);
  72.             dp_before = dp_curr;
  73.         }
  74.         cout << dp_before[n] << endl;
  75.     }
  76. }
Success #stdin #stdout 0.07s 198788KB
comments (?)
stdin
copy 
2
5 1
1 2 3 4 5
5 2
5 4 3 2 1
stdout
copy 
0
13
https://ideone.com/arclhm
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!