fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. typedef vector<int> vi;
  5. typedef pair <int, int> ii;
  6. typedef pair <ll, int> li;
  7. #define mk make_pair
  8.  
  9. const int N = 2e5 + 5;
  10.  
  11. int n, k;
  12. int a[1005];
  13. int dp[1005][1005];
  14. /*
  15.     80  10  5   7   100 20  35
  16. 0   
  17. 1
  18. 2
  19. 	MAI YEU ANH J97 AKA TRINH TRAN PHUONG TUAN AKA JACK 3.5MM
  20.  
  21. */
  22.  
  23. int main()
  24. {
  25.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  26.     // #define file "VNOJ"
  27.     // freopen(file".INP", "r", stdin);
  28.     // freopen(file".OUT", "w", stdout);
  29.  
  30.  
  31.     cin >> n >> k;
  32.  
  33.     for (int i = 1; i <= n; i++) cin >> a[i];
  34.  
  35.     fill (&dp[0][0], &dp[0][0] + (1005 * 1005), INT_MAX);
  36.  
  37.  
  38.     int mx = a[1], s = a[1];
  39.  
  40.  
  41.     dp[0][0] = dp[0][1] = 0;
  42.     for (int i = 2; i <= n; i++)
  43.     {
  44.         s += a[i];
  45.         mx = max(mx, a[i]);
  46.         dp[0][i] = mx * i - s;
  47.     }
  48.  
  49.     for (int i = 1; i <= k; i++)
  50.     {
  51.         for (int j = 1; j <= n; j++)
  52.         {
  53.             if (j < i + 1)
  54.             {
  55.                 dp[i][j] = 0;
  56.             }
  57.             {
  58.                 int r = j;
  59.                 s = 0; mx = 0;
  60.                 while (r > i)
  61.                 {
  62.                     s += a[r]; mx = max(a[r], mx);
  63.                     dp[i][j] = min(dp[i][j], mx * (j - r + 1) - s + dp[i - 1][r - 1]);
  64.                     // cout << a[r] << ' ' << mx * (j - r + 1) - s + dp[i - 1][j - 1] << '\n';
  65.                     r--;
  66.                 }
  67.                 // cout << "__________\n";
  68.             }
  69.         }
  70.     }
  71.  
  72.  
  73.     // for (int i = 0; i <= k; i++)
  74.     // {
  75.     //     for (int j = 1; j <= n; j++)
  76.     //     {
  77.     //         cout << dp[i][j] << ' ';
  78.     //     }
  79.     //     cout << '\n';
  80.     // }
  81.  
  82.     cout << dp[k][n];
  83.  
  84.  
  85.  
  86.  
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 7584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L7hZxn
language:
C++14 (gcc 8.3)
created:
5 days 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!