Advertisement
Saleh127

UVA 10003 / DP

Nov 23rd, 2021
732
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-23-22.43.31
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11.  
  12. ll dp[55][55];
  13.  
  14. ll a[2005];
  15.  
  16. ll solve(ll i,ll j)
  17. {
  18.  
  19.     if(j-i<=1) return 0ll;
  20.  
  21.     ll &ans=dp[i][j];
  22.  
  23.     if(ans==-1)
  24.     {
  25.         ans=INT_MAX;
  26.         for(ll k=i; k<=j; k++)
  27.         {
  28.             ans=min(ans,solve(i,k)+solve(k,j)+a[j]-a[i]);
  29.         }
  30.     }
  31.  
  32.     return ans;
  33.  
  34. }
  35.  
  36. int main()
  37. {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.  
  42.     ll n,l;
  43.  
  44.     while(cin>>l && l)
  45.     {
  46.         cin>>n;
  47.  
  48.         a[0]=0;
  49.  
  50.         for(ll i=1; i<=n; i++)
  51.         {
  52.             cin>>a[i];
  53.         }
  54.  
  55.         a[n+1]=l;
  56.  
  57.         for(ll i=0; i<=n+2; i++)
  58.         {
  59.             for(ll j=0; j<=n+2; j++)
  60.             {
  61.                 dp[i][j]=-1;
  62.             }
  63.         }
  64.  
  65.         cout<<"The minimum cutting is "<<solve(0,n+1)<<"."<<nl;
  66.     }
  67.  
  68.  
  69.  
  70.     get_lost_idiot;
  71. }
  72.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement