This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
long long n,a[10001];
void read()
{
cin>>n;
for(long long i=1;i<=n;i++)
cin>>a[i];
}
long long dp[10001][10001];
long long dl[10005],dr[10005];
void prec()
{
for(long long i=1;i<=n;i++)
{
dl[i]=dl[i-1];
if(a[i]==-1)dl[i]=i;
}
for(long long i=n;i>=1;i--)
{
dr[i]=dr[i+1];
if(a[i]==-1)dr[i]=i;
}
}
void solve()
{
prec();
for(long long i=0;i<=n;i++)
{
for(long long j=0;j<=2*n;j++)
{
dp[i][j]=-1e9;
}
}
long long sum=0;
for(long long i=1;i<=n;i++)
{
//cout<<i<<" "<<dl[i]<<" "<<dr[i]<<endl;
if(a[i]==1)dp[i][i]=1,sum++;
}
long long ans=0;
dp[0][0]=0;
for(long long i=1;i<=n;i++)
{
if(a[i]!=1)continue;
for(long long j=i;j<=2*i;j++)
{
for(long long pr=1;pr<i;pr++)
{
if(a[pr]!=1)continue;
if(dl[pr])
{
long long d=dl[pr];
long long f=j-(abs(d-i)+abs(d-pr));
if(f>=0)dp[i][j]=max(dp[i][j],dp[pr][f]+1);
}
if(dr[pr])
{
long long d=dr[pr];
long long f=j-(abs(d-i)+abs(d-pr));
if(f>=0)dp[i][j]=max(dp[i][j],dp[pr][f]+1);
}
}
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
ans=max(ans,dp[i][j]);
}
}
cout<<sum-ans<<endl;
}
int main()
{
speed();
read();
solve();
return 0;
}
/*
7
1 0 1 -1 -1 1 1
7
-1 1 0 0 -1 0 0
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |