Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## dp水过

Posted by 814264306 at 2019-04-19 15:28:16 on Problem 1905
```#include<iostream>
using namespace std;
//3 4 5 2 1 5 4 3
void maxList(double a[],int n,int lis[])
{
int *dp = new int[n+1];
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = 1;
for (int j = 1; j < i; j++)
{
if (dp[j] + 1 > dp[i] && a[i] > a[j])
{
dp[i] = dp[j] + 1;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (ans < dp[i])ans = dp[i];
lis[i] = ans;
}
}

void minList(double a[], int n,int size,int lms[])
{
double *b=new double[size-n+1];
for (int i = n + 1; i <= size; i++)
{
b[i - n] = a[size - i+n+1];
}
maxList(b, size - n,lms);

}

int main()
{
double a[1010];
int n,ans=0,lis[1010],lms[1010];
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}

maxList(a, n, lis);
minList(a, 0, n,  lms);
lis[0] = 0;
lms[0] = 0;
for (int i = 0; i <= n; i++)
{
int g = lis[i] + lms[n-i];
//cout << lis[i] << "   ";
//cout << lms[n-i] << endl;
if (ans < g)ans = g;
}
cout << n - ans << endl;
}```

Followed by: