Advertisement
YEZAELP

CUBE-104: Tasty Chocolate

Aug 20th, 2020
119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. int ar[1001];
  6. int n, MX = 0;
  7. vector <vector<int>> dp(1001, vector<int> (3001,INF));
  8.  
  9. int f(int i, int mx){
  10.  
  11.     if(i == n) {
  12.         if(ar[i] <= mx)
  13.             return dp[i][mx] = 1;
  14.         return dp[i][mx] = 0;
  15.     }
  16.  
  17.     if(dp[i][mx] != INF) return dp[i][mx];
  18.  
  19.     for(int j = mx+1; j <= MX; j++){
  20.         int x = f(i+1, j);
  21.         if(j == ar[i]) dp[i][mx] = min(dp[i][mx], x);
  22.         else dp[i][mx] = min(dp[i][mx], x + 1);
  23.     }
  24.  
  25.     return dp[i][mx];
  26. }
  27.  
  28. int main(){
  29.  
  30.     scanf("%d",&n);
  31.     for(int i=1;i<=n;i++){
  32.         scanf("%d",&ar[i]);
  33.         MX = max(MX, ar[i]);
  34.     }
  35.  
  36.     printf("%d", f(1,0));
  37.  
  38.     return 0;
  39. }
  40.  
Advertisement
RAW Paste Data Copied
Advertisement