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;
}