Advertisement
YEZAELP

o58_oct_c2_defense

Oct 25th, 2021
569
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 N = 3e3 + 10;
  5. const int INF = 1e9;
  6. int ar[N], dp[N];
  7. int n, k;
  8.  
  9. int main(){
  10.  
  11.     scanf("%d%d", &n, &k);
  12.  
  13.     for(int i=1;i<=n;i++){
  14.         scanf("%d", &ar[i]);
  15.         dp[i] = INF;
  16.     }
  17.  
  18.     if(n <= k){
  19.         dp[1] = ar[1];
  20.         int mn = ar[1];
  21.         int ans = INF;
  22.         for(int i=2;i<=n;i++){
  23.             ans = min(ans, ar[i] + mn);
  24.             mn = min(mn, ar[i]);
  25.         }
  26.         printf("%d", ans);
  27.     }
  28.     else if(n >= 2 * k){
  29.         dp[1] = ar[1];
  30.         int mn = ar[1];
  31.         for(int i=2;i<=k;i++){
  32.             dp[i] = ar[i] + mn;
  33.             mn = min(mn, ar[i]);
  34.         }
  35.  
  36.         for(int i=k+1;i<n;i++){
  37.             for(int j=i-k+1;j<i;j++){
  38.                 dp[i] = min(dp[i], ar[i] + dp[j]);
  39.             }
  40.         }
  41.  
  42.         int ans = INF;
  43.         for(int i=n-k+2;i<=n;i++){
  44.             for(int j=i-k+1;j<i;j++){
  45.                 ans = min(ans, ar[i] + dp[j]);
  46.             }
  47.         }
  48.         printf("%d", ans);
  49.     }
  50.     else{
  51.         dp[1] = ar[1];
  52.         int mn = ar[1];
  53.         for(int i=2;i<=k;i++){
  54.             dp[i] = ar[i] + mn;
  55.             mn = min(mn, ar[i]);
  56.         }
  57.  
  58.         int ans = INF;
  59.         for(int i=k+1;i<=n;i++){
  60.             for(int j=i-k+1;j<i;j++){
  61.                 ans = min(ans, ar[i] + dp[j]);
  62.             }
  63.         }
  64.         printf("%d", ans);
  65.     }
  66.  
  67.     return 0;
  68. }
Advertisement
RAW Paste Data Copied
Advertisement