#include <iostream> #include <vector> using namespace std; int main() { int n, i, j, k; long long w=0, p=0; cin>>n; vector <int> v, va, m1, m2; int t[n]; for (i=0; i<n; i++) { cin>>t[i]; if (t[i]!=0) { v.push_back(w); va.push_back(k); k=1; } else { k++; } w=w+t[i]; } for (i=1; i<v.size(); i++) { p=w-v[i]; if (p>=0 && v[i]>=0) { m1.push_back(v[i]); m2.push_back(va[i]); } } if (m1.size()==0) { cout<<-1; return 0; } int y[m1.size()]; y[m1.size()-1]=m2[m1.size()-1]; w=y[m1.size()-1]; for (i=m1.size()-2; i>=0; i--) { y[i]=m2[i]; for (j=i+1; j<m1.size(); j++) { if (m1[i]<=m1[j]) { if (m2[i]+y[j]>y[i]) { y[i]=m2[i]+y[j]; } } } if (y[i]>w) { w=y[i]; } } i=0; k=0; while (t[i]==0) { k++; i++; } i=n-1; while (t[i]==0) { k++; i--; } cout<<n-1-w-k; 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 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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #include <iostream> #include <vector> using namespace std; int main() { int n, i, j, k; long long w=0, p=0; cin>>n; vector <int> v, va, m1, m2; int t[n]; for (i=0; i<n; i++) { cin>>t[i]; if (t[i]!=0) { v.push_back(w); va.push_back(k); k=1; } else { k++; } w=w+t[i]; } for (i=1; i<v.size(); i++) { p=w-v[i]; if (p>=0 && v[i]>=0) { m1.push_back(v[i]); m2.push_back(va[i]); } } if (m1.size()==0) { cout<<-1; return 0; } int y[m1.size()]; y[m1.size()-1]=m2[m1.size()-1]; w=y[m1.size()-1]; for (i=m1.size()-2; i>=0; i--) { y[i]=m2[i]; for (j=i+1; j<m1.size(); j++) { if (m1[i]<=m1[j]) { if (m2[i]+y[j]>y[i]) { y[i]=m2[i]+y[j]; } } } if (y[i]>w) { w=y[i]; } } i=0; k=0; while (t[i]==0) { k++; i++; } i=n-1; while (t[i]==0) { k++; i--; } cout<<n-1-w-k; return 0; } |