Advertisement
YEZAELP

PROG-1093: หยิบหนังสือ

Nov 11th, 2021
680
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. const int N = 2e3 + 1;
  6. int dp[2][N];
  7. int ar[N];
  8. int n;
  9.  
  10. int f(int i, int s){
  11.  
  12.     if(i == n + 1){
  13.         if(s == 0) return 0;
  14.         else return -INF;
  15.     }
  16.  
  17.     if(dp[i][s] != -INF) return dp[i][s];
  18.  
  19.     dp[i][s] = ar[i] + f(i + 1, s + 1);
  20.     if(s == 0) dp[i][s] = max(dp[i][s], f(i + 1, s));
  21.     if(s >= 2) dp[i][s] = max(dp[i][s], - ar[i] + f(i + 1, s - 2));
  22.  
  23.     return dp[i][s];
  24. }
  25.  
  26. int main(){
  27.  
  28.     scanf("%d", &n);
  29.  
  30.     for(int i=1;i<=n;i++){
  31.         scanf("%d", &ar[i]);
  32.     }
  33.  
  34.     int pre, cur;
  35.     cur = (n + 1) % 2;
  36.     dp[cur][0] = 0;
  37.     for(int s=1;s<=n;s++){
  38.         dp[cur][s] = -INF;
  39.     }
  40.  
  41.     for(int i=n;i>=1;i--){
  42.         pre = (i + 1) % 2;
  43.         cur = i % 2;
  44.         for(int s=n;s>=0;s--){
  45.             dp[cur][s] = ar[i] + dp[pre][s + 1];
  46.             if(s == 0) dp[cur][s] = max(dp[cur][s], dp[pre][s]);
  47.             if(s >= 2) dp[cur][s] = max(dp[cur][s], - ar[i] + dp[pre][s - 2]);
  48.         }
  49.     }
  50.  
  51.     printf("%d", dp[1][0]);
  52.  
  53.     return 0;
  54. }
Advertisement
RAW Paste Data Copied
Advertisement