mickypinata

KOI: Resort

Dec 6th, 2021
654
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 N = 100 + 5;
  5. const int C = 40 + 5;
  6.  
  7. int dp[N][C];
  8. bool isFree[N];
  9.  
  10. int main(){
  11.  
  12.     int n, nNotFree;
  13.     scanf("%d%d", &n, &nNotFree);
  14.     for(int i = 1; i <= n; ++i){
  15.         isFree[i] = true;
  16.     }
  17.     for(int i = 1; i <= nNotFree; ++i){
  18.         int x;
  19.         scanf("%d", &x);
  20.         isFree[x] = false;
  21.     }
  22.     int mxCoupon = n / 5 * 2;
  23.     for(int i = n; i >= 1; --i){
  24.         for(int c = 0; c <= mxCoupon; ++c){
  25.             if(!isFree[i]){
  26.                 dp[i][c] = dp[i + 1][c];
  27.                 continue;
  28.             }
  29.             int mn = 1e9;
  30.             if(c >= 3){
  31.                 mn = min(mn, dp[i + 1][c - 3]);
  32.             }
  33.             if(i + 4 <= n){
  34.                 mn = min(mn, 37000 + dp[i + 5][c + 2]);
  35.             }
  36.             if(i + 2 <= n){
  37.                 mn = min(mn, 25000 + dp[i + 3][c + 1]);
  38.             }
  39.             mn = min(mn, 10000 + dp[i + 1][c]);
  40.             dp[i][c] = mn;
  41.         }
  42.     }
  43.     cout << dp[1][0];
  44.  
  45.     return 0;
  46. }
  47.  
RAW Paste Data