#include <bits/stdc++.h> using namespace std; const long long inf = 999999999; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int tab[n + 1]; long long pref[n + 1]; pref[0] = 0; tab[0] = 0; for(int i = 1; i <= n; i ++) { cin >> tab[i]; pref[i] = tab[i] + pref[i - 1]; } int d[n + 1]; d[0] = 0; for(int i = 1; i <= n; i ++) d[i] = -inf; for(int i = 1; i <= n; i ++) { for(int k = 1; k <= i; k ++) { if(pref[i] - pref[k - 1] >= 0) d[i] = max(d[i], d[k - 1] + 1); } } if(d[n] <= 0) cout << -1; else cout << n - d[n]; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <bits/stdc++.h> using namespace std; const long long inf = 999999999; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int tab[n + 1]; long long pref[n + 1]; pref[0] = 0; tab[0] = 0; for(int i = 1; i <= n; i ++) { cin >> tab[i]; pref[i] = tab[i] + pref[i - 1]; } int d[n + 1]; d[0] = 0; for(int i = 1; i <= n; i ++) d[i] = -inf; for(int i = 1; i <= n; i ++) { for(int k = 1; k <= i; k ++) { if(pref[i] - pref[k - 1] >= 0) d[i] = max(d[i], d[k - 1] + 1); } } if(d[n] <= 0) cout << -1; else cout << n - d[n]; return 0; } |