SHARE
TWEET

Knuth optimization

_Muhammad Oct 23rd, 2019 98 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. typedef long long ll;
  7. const int inf = 2000000000;
  8.  
  9. #define mem(a,b) memset(a, b, sizeof(a) )
  10. #define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  11.  
  12. const int mx = 1e3+123;
  13. long long dp[mx][mx], c[mx];
  14. int opt[mx][mx];
  15.  
  16. int main()
  17. {
  18.     optimize();
  19.  
  20.     ll m, n;
  21.     while ( cin >> m >> n ) {
  22.         mem ( dp, 0 );
  23.         c[n+1] = m;
  24.  
  25.         for ( int i = 1; i <= n; i++ ) cin >> c[i];
  26.  
  27.         for ( int i = 0; i <= n+1; i++ ) {
  28.             for ( int l = 0; l+i <= n+1; l++ ) {
  29.                 int r = l + i;
  30.  
  31.                 if ( i < 2 ) {
  32.                     dp[l][r] = 0;
  33.                     opt[l][r] = l;
  34.                     continue;
  35.                 }
  36.  
  37.                 int ml = opt[l][r-1];
  38.                 int mr = opt[l+1][r];
  39.  
  40.                 dp[l][r] = inf;
  41.                 for ( int k = ml; k <= mr; k++ ) {
  42.                     int d = dp[l][k] + dp[k][r] + c[r] - c[l];
  43.                     if ( dp[l][r] > d ) {
  44.                         dp[l][r] = d;
  45.                         opt[l][r] = k;
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.  
  51.         cout << dp[0][n+1] << endl;
  52.     }
  53.  
  54.     return 0;
  55. }
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
 
Top