Paste Search Dynamic
Recent pastes
pre sum
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. int pre_sum[10];
  5. int dp[10][10];
  6. int f(int i, int n, int S) {
  7.         cout<<i<<" "<<S<<"n";
  8.         if(i>n) return 0;
  9.         if(dp[i][S]!=-1) return dp[i][S];
  10.         int rem_ele1=n-i+1;
  11.         if(rem_ele1<=2*S) return pre_sum[n]-pre_sum[i-1];
  12.         dp[i][S]=0;
  13.         // for(int k1=1;k1<=2*S;k1++) {
  14.         //      S=max(S,k1);
  15.         //      int sum=pre_sum[i+k1-1]-pre_sum[i-1];
  16.         //      int m=INT_MAX;
  17.         //      for(int k2=1;k2<=2*S;k2++) {
  18.         //              S=max(S,k2);
  19.         //              if(i+k1+k2>n) break;
  20.         //              m=min(m,f(i+k1+k2,n,S));
  21.         //      }
  22.         //      dp[i][S]=max(dp[i][S],m);
  23.         // }
  24.         return dp[i][S];
  25. }
  26. int main() {
  27.         int a[6]={0, 3, 6, 8, 5, 4};
  28.         int n=5;
  29.         pre_sum[1]=a[1];
  30.         for(int i=2;i<=n;i++) pre_sum[i]=a[i]+pre_sum[i-1];
  31.         for(int i=1;i<=n;i++) {
  32.                 cout<<i<<" "<<pre_sum[i]<<"n";
  33.         }
  34.         memset(dp,-1,sizeof(dp));
  35.         cout<<f(1,5,1);
  36.         cout<<dp[1][1];
  37.         return 0;
  38. }
Parsed in 0.007 seconds