SHARE
TWEET

Partition dp trick

_Muhammad Oct 22nd, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6.  
  7. const int mx = 5e3+123;
  8. int n, num[mx], dp[mx], c[mx][mx], a[mx];
  9.  
  10.  
  11. /// Here l, r is range and p is optimal solution
  12. struct node {
  13.     int l, r, p;
  14.     node(){}
  15.     node ( int _l, int _r, int _p ) : l (_l), r (_r), p (_p) {
  16.  
  17.     }
  18. };
  19.  
  20. node que[mx];
  21.  
  22.  
  23. /// This function compares if i is better ans than j for k
  24. bool cmp ( int i, int j, int k )
  25. {
  26.     int v1 = dp[i] + c[i+1][k], v2 = dp[j] + c[j+1][k];
  27.     if ( v1 == v2 ) return num[i] <= num[j];
  28.     return ( v1 < v2 );
  29. }
  30.  
  31.  
  32.  
  33.  
  34. /// This function finds the lowest position where i is optimal solution in node cur
  35. int find ( node cur, int i )
  36. {
  37.     int l = cur.l, r = cur.r+1;
  38.     while ( l < r ) {
  39.         int mid = ( l + r ) >> 1;
  40.         if ( cmp ( i, cur.p, mid ) ) r = mid;
  41.         else l = mid+1;
  42.     }
  43.  
  44.     return r;
  45. }
  46.  
  47.  
  48.  
  49.  
  50. int solve (  int mid )
  51. {
  52.     int s = 1, t = 1;
  53.     dp[0] = num[0] = 0;
  54.     que[1] = node ( 1, n, 0 ); /// Initilaising optimal value of all index as 0.
  55.  
  56.     for ( int i = 1; i <= n; i++ ) {
  57.         while ( s < t && que[s].r < i ) s++; /// Deleting ranges from front until we get the range where i index lies
  58.         dp[i] = dp[que[s].p] + c[que[s].p+1][i] + mid; /// calculating dp[i] with slop mid
  59.         num[i] = num[que[s].p] + 1; /// calculating num[i].
  60.  
  61.         if ( cmp ( i, que[t].p, n ) ) { /// Checking if i is better than the current optimal value of last range
  62.             while ( s <= t && cmp ( i, que[t].p, que[t].l ) ) t--; /// Deleting all range from back of queue where i is better.
  63.             if ( s > t ) que[++t] = node ( i+1, n, i ); /// Creating new range when deque is empty.
  64.             else {
  65.                 int pos = find( que[t], i ); /// Finding lowest position where i is optimal solution.
  66.                 que[t].r = pos-1;
  67.                 que[++t] = node ( pos, n, i ); /// Creating new range.
  68.             }
  69.         }
  70.     }
  71.  
  72.     return num[n];
  73. }
  74.  
  75.  
  76. int main()
  77. {
  78.     int k;
  79.     cin >> n >> k;
  80.     for ( int i = 1; i <= n; i++ ) cin >> a[i];
  81.  
  82.     for ( int i = 1; i <= n; i++ ) {
  83.         for ( int j = i; j <= n; j++ ) cin >> c[i][j];
  84.     }
  85.  
  86.     int l = 0, r = 3e7+123, ans = 0;
  87.  
  88.     /// Binary search on slop
  89.     while ( l <= r ) {
  90.         int mid = ( l + r ) >> 1;
  91.         if ( solve ( mid ) <= k ) {
  92.             ans = dp[n] - ( k * mid ); /// As mid is added in dp[n], k times.
  93.             r = mid-1;
  94.         }
  95.  
  96.         else l = mid+1;
  97.     }
  98.  
  99.     cout << ans << endl;
  100.  
  101.  
  102.     return 0;
  103. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top