Advertisement
astral17

1_3

Mar 27th, 2019
46
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int dp[2005][2005];
  6. int sum[2005][2005];
  7. int tree[8005];
  8.  
  9. void update(int v, int tl, int tr, int pos)
  10. {
  11.     if (tl == tr)
  12.     {
  13.         tree[v] = 1;
  14.         return;
  15.     }
  16.     int tm = (tl + tr) >> 1;
  17.     if (pos <= tm)
  18.         update(v * 2, tl, tm, pos);
  19.     else
  20.         update(v * 2 + 1, tm + 1, tr, pos);
  21.     tree[v] = tree[v * 2] + tree[v * 2 + 1];
  22. }
  23.  
  24. int findSum(int v, int tl, int tr, int l, int r)
  25. {
  26.     if (l > r)
  27.         return 0;
  28.     if (tl == l && tr == r)
  29.         return tree[v];
  30.     int tm = (tl + tr) >> 1;
  31.     return findSum(v * 2, tl, tm, l, min(r, tm)) +
  32.            findSum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  33. }
  34.  
  35. vector<int> v, pos;
  36.  
  37. bool IsLess(int a, int b)
  38. {
  39.     return v[a] < v[b];
  40. }
  41.  
  42. int main()
  43. {
  44.     ifstream cin("input.txt");
  45.     ofstream cout("output.txt");
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(0);
  48.     cout.tie(0);
  49.     int n, k;
  50.     cin >> n >> k;
  51.     v.resize(n);
  52.     pos.resize(n);
  53.     for (int i = 0; i < n; i++)
  54.     {
  55.         cin >> v[i];
  56.         pos[i] = i;
  57.     }
  58.     sort(pos.begin(), pos.end(), IsLess);
  59.     for (int i = 0; i < n; i++)
  60.         v[ pos[i] ] = i;
  61.  
  62.     for (int i = 0; i < n; i++)
  63.     {
  64.         fill(tree, tree + 8005, 0);
  65.         update(1, 0, n - 1, v[i]);
  66.         for (int j = i + 1; j < n; j++)
  67.         {
  68.             sum[i][j] = sum[i][j - 1] + findSum(1, 0, n - 1, v[j], n - 1);
  69.             update(1, 0, n - 1, v[j]);
  70.         }
  71.     }
  72.     fill(dp[0], dp[0] + 100000, -1e9 + 7);
  73.     for (int i = 0; i < n; i++)
  74.         dp[0][i] = sum[0][i];
  75.  
  76.     for (int i = 1; i < k; i++)
  77.         for (int j = i; j < n; j++)
  78.         {
  79.             dp[i][j] = 1e9 + 7;
  80.             for (int z = 1; z <= j - i + 1; z++)
  81.                 dp[i][j] = min(dp[i][j], dp[i - 1][j - z] + sum[j - z + 1][j]);
  82.         }
  83.     cout << dp[k - 1][n - 1];
  84.     return 0;
  85. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement