Advertisement
YEZAELP

CUBE-104: Tasty Chocolate_bottom up

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