#include<cstdio> #include<utility> #include<vector> typedef std::pair<int, int> pii; typedef std::vector<pii> vpii; typedef long long ll; int n; vpii v; void input() { scanf("%d", &n); int a; int last = 0; for (int i = 0; i < n; i++) { scanf("%d", &a); if (a != 0) { v.push_back(std::make_pair(i - last, a)); last = i; // printf("%d %d\n", v[v.size() - 1].first, v[v.size() - 1].second); } } } int min(int & a, int & b) { return a < b ? a : b; } int solve(int i, ll curr, int len) { pii p = v[i]; if (i == v.size()) { if (curr < 0) { return -1; } return len; } if (curr < 0) { return solve(i + 1, curr + p.second, len + p.first); } int s1 = solve(i + 1, p.second, len); int s2 = solve(i + 1, curr + p.second, len + p.first); if (s1 < 0) { return s2; } else if (s2 < 0) { return s1; } return min(s1, s2); } int solve() { return solve(0, 0ll, 0); } int main() { input(); printf("%d\n", solve()); }
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include<cstdio> #include<utility> #include<vector> typedef std::pair<int, int> pii; typedef std::vector<pii> vpii; typedef long long ll; int n; vpii v; void input() { scanf("%d", &n); int a; int last = 0; for (int i = 0; i < n; i++) { scanf("%d", &a); if (a != 0) { v.push_back(std::make_pair(i - last, a)); last = i; // printf("%d %d\n", v[v.size() - 1].first, v[v.size() - 1].second); } } } int min(int & a, int & b) { return a < b ? a : b; } int solve(int i, ll curr, int len) { pii p = v[i]; if (i == v.size()) { if (curr < 0) { return -1; } return len; } if (curr < 0) { return solve(i + 1, curr + p.second, len + p.first); } int s1 = solve(i + 1, p.second, len); int s2 = solve(i + 1, curr + p.second, len + p.first); if (s1 < 0) { return s2; } else if (s2 < 0) { return s1; } return min(s1, s2); } int solve() { return solve(0, 0ll, 0); } int main() { input(); printf("%d\n", solve()); } |