fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. int main() {
  5. 	int n;cin>>n;
  6. 	vector<ll>a(n);
  7. 	for(int i = 0;i<n;i++){
  8. 		cin>>a[i];
  9. 	}
  10.  
  11.  
  12.     vector<vector<ll>>dp(n,vector<ll>(100+1,1e18));
  13.     dp[0][a[0]]=0;
  14.     //dp[0][0]=0;
  15.     for(int i = 1 ;i < n ;i++){
  16.     	int sum = 0;
  17.     	for(int j = i ; j >=0;j--){
  18.     		int l = i-j;
  19.     		 sum+=a[j];
  20.     		 if (sum > 100) break;
  21.     		for(int sum1 = 0;sum1<=sum;sum1++){
  22.     	      dp[i][sum] = min(dp[i][sum],(j > 0 ? dp[j-1][sum1] : (sum1 == 0 ? 0 : (ll)1e18)) + l);		
  23.     		}
  24.     	}
  25.     }
  26.  
  27.     long long ans = 1e18;
  28.     for(int i = 0;i<=100;i++){
  29.     	if(dp[n-1][i]<1e18){
  30.     		ans =  min(ans,dp[n-1][i]);
  31.     	}
  32.     }
  33.     cout<<ans;
  34. 	return 0;
  35. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
5
1 8 1 9 10
stdout
copy 
1
https://ideone.com/kkW37o
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!