fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define pii pair<int,int>
  5. #define fi first
  6. #define se second
  7. #define FOR(i,a,b) for(int i=(a); i<=(b); i++)
  8. #define el '\n'
  9.  
  10. const int maxN = 2e5 + 5;
  11. const int LOG = 18;
  12. const ll inf = 1e18; // Dùng ll để tránh tràn số
  13.  
  14. int n;
  15. pii lim;
  16. int a[maxN];
  17.  
  18. // Sparse Table để truy vấn max/min đoạn O(1)
  19. int maxVal[maxN][LOG + 5], minVal[maxN][LOG + 5];
  20.  
  21. int getMax(int l, int r) {
  22.     int k = 31 - __builtin_clz(r - l + 1);
  23.     return max(maxVal[l][k], maxVal[r - (1 << k) + 1][k]);
  24. }
  25.  
  26. int getMin(int l, int r) {
  27.     int k = 31 - __builtin_clz(r - l + 1);
  28.     return min(minVal[l][k], minVal[r - (1 << k) + 1][k]);
  29. }
  30.  
  31. void solve() {
  32.     // 1. Xây dựng Sparse Table O(N log N)
  33.     FOR(i, 1, n) {
  34.         maxVal[i][0] = a[i];
  35.         minVal[i][0] = a[i];
  36.     }
  37.     for (int j = 1; (1 << j) <= n; j++) {
  38.         for (int i = 1; i + (1 << j) - 1 <= n; i++) {
  39.             maxVal[i][j] = max(maxVal[i][j - 1], maxVal[i + (1 << (j - 1))][j - 1]);
  40.             minVal[i][j] = min(minVal[i][j - 1], minVal[i + (1 << (j - 1))][j - 1]);
  41.         }
  42.     }
  43.  
  44.     // 2. Tối ưu DP cho N lớn
  45.     // Nếu đề bài cho phép tìm min chi phí chia mảng thành bất kỳ số lượng đoạn nào:
  46.     vector<ll> dp(n + 1, inf);
  47.     dp[0] = 0;
  48.  
  49.     FOR(i, 1, n) {
  50.         // Thử các độ dài k hợp lệ cho đoạn kết thúc tại i (từ lim.fi đến lim.se)
  51.         FOR(k, lim.fi, lim.se) {
  52.             int prev_idx = i - k;
  53.             if (prev_idx < 0) break; // k tăng dần, nếu âm thì break sớm
  54.  
  55.             if (dp[prev_idx] != inf) {
  56.                 int mx = getMax(prev_idx + 1, i);
  57.                 int mn = getMin(prev_idx + 1, i);
  58.                 ll val = mx - mn;
  59.                 dp[i] = min(dp[i], dp[prev_idx] + val);
  60.             }
  61.         }
  62.     }
  63.  
  64.     if (dp[n] == inf) cout << -1 << el;
  65.     else cout << dp[n] << el;
  66. }
  67.  
  68. int main() {
  69.     ios_base::sync_with_stdio(0); cin.tie(0);
  70.  
  71.     if (!(cin >> n >> lim.fi >> lim.se)) return 0;
  72.     FOR(i, 1, n) cin >> a[i];
  73.  
  74.     solve();
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2yIdiX
8 2 3
4 9 5 1 8 2 7 3
language:
C++ (gcc 8.3)
created:
14 hours 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!