Advertisement
YEZAELP

CUBE-104: Tasty Chocolate_top down

Aug 25th, 2020 (edited)
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. int ar[1001];
  6. int n;
  7. vector <vector<int>> dp(1001, vector<int> (3001,INF));
  8.  
  9. int f(int i, int mx){
  10.  
  11.     if(mx > 3000) return INF;
  12.     if(i > n) return 0;
  13.  
  14.     if(dp[i][mx] != INF) return dp[i][mx];
  15.  
  16.     if(ar[i] > mx )
  17.         dp[i][mx] = min( f(i + 1, mx + 1) + 1, f(i + 1, ar[i]));
  18.         // ลดค่าให้น้อยลง หรือ ใช้ค่านั้นๆไปเลย
  19.     else
  20.         dp[i][mx] =  f(i + 1, mx + 1) + 1;
  21.         // เพิ่มค่าได้เท่านั้น
  22.     return dp[i][mx];
  23. }
  24.  
  25. int main(){
  26.  
  27.     scanf("%d",&n);
  28.     for(int i=1;i<=n;i++)
  29.         scanf("%d",&ar[i]);
  30.  
  31.     printf("%d", f(1,0));
  32.  
  33.     return 0;
  34. }
  35.  
Advertisement
RAW Paste Data Copied
Advertisement