Advertisement
YEZAELP

CUBE-013: B-Partition

Aug 15th, 2020
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4.  
  5. int n,k;
  6. int qs[1001];
  7. vector <vector<int>> dp(1001, vector <int> (301,INF));
  8.  
  9. int f(int i, int j){// n, k
  10.  
  11.     if(i > n) return INF;
  12.     if(j == k) {
  13.         return qs[n] - qs[i-1];
  14.     }
  15.  
  16.     if(dp[i][j] != INF) return dp[i][j];
  17.  
  18.     for(int l=i;l<=n;l++){
  19.         dp[i][j] = min(dp[i][j], max(qs[l]-qs[i-1], f(l+1,j+1)));
  20.     }
  21.     return dp[i][j];
  22. }
  23.  
  24. int main(){
  25.  
  26.     scanf("%d%d",&n,&k);
  27.  
  28.     for(int i=1;i<=n;i++){
  29.         scanf("%d",&qs[i]);
  30.         qs[i] += qs[i-1];
  31.     }
  32.  
  33.     for(int i=n;i>=1;i--){
  34.         for(int j=k;j>=1;j--){
  35.             if(j == k) dp[i][j] = qs[n] - qs[i-1];
  36.             for(int l=i;l<=n;l++){
  37.                 if(j+1 > k) continue;
  38.                 if(l+1 > n) dp[i][j] = min(dp[i][j], qs[l]-qs[i-1]);
  39.                 else dp[i][j] = min(dp[i][j], max(qs[l]-qs[i-1], dp[l+1][j+1]));
  40.             }
  41.         }
  42.     }
  43.     printf("%d",dp[1][1]);
  44.     //printf("%d",f(1,1));
  45.     return 0;
  46. }
  47.  
Advertisement
RAW Paste Data Copied
Advertisement