# P1091 chorus formation (DP & LIS)

2021-08-10 08:05:07

## P1091 Chorus formation (DP&LIS)

Subject portal

Ideas ： Obviously running both sides LIS, Go through it and get the most value . Time complexity ：O（n^2) But it can be used upper_bound() Press to O(nlogn) This practice is not written here ....

AC Code ：

``````#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],dp[2][N];// preservation [1,n] and [n,1] Of LIS
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dp[0][1]=dp[1][n]=1;
for(int i=2,mx;i<=n;i++){ // Run both sides LIS
mx=0;
for(int j=1;j<i;j++)
if(a[j]<a[i]&&dp[0][j]>mx)
mx=dp[0][j];
dp[0][i]=mx+1;
}
for(int i=n-1,mx;i>=1;i--){
mx=0;
for(int j=n;j>i;j--)
if(a[j]<a[i]&&dp[1][j]>mx)
mx=dp[1][j];
dp[1][i]=mx+1;
}
int ans=0;
for(int i=1;i<=n;i++)// Traverse to get the maximum value .
ans=max(ans,dp[0][i]+dp[1][i]-1);
printf("%d\n",n-ans);
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.
```

https://chowdera.com/2021/08/20210810080205615z.html