• API
• FAQ
• Tools
• Archive
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 = num = 0;
54.     que = 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.
Not a member of Pastebin yet?