G - Association for the Country of Mububa (dp)

    科技2022-07-12  210

    #include<bits/stdc++.h> #define ll long long using namespace std; const int N=3e3+100; ll a[N]; ll dp[N]; ll sum[N]; int num[N]; int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } for(int i=1;i<=n;i++){ for(int j=i-1;j>=0;j--){ if(sum[i]-sum[j]>=dp[j]){ dp[i]=sum[i]-sum[j]; num[i]=num[j]+1; break; } } } printf("%d\n",num[n]); return 0; }

     

    Processed: 0.011, SQL: 8