简单

#include<bits/stdc++.h>
using namespace std;
int t[102],dp1[102],dp2[102],n,ans;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&t[i]);
    t[0]=0;t[n+1]=0;
    memset(dp1,0,sizeof(dp1));
    for (int i=1;i<=n;i++)
        for (int j=0;j<i;j++)
            if (t[i]>t[j])
                dp1[i]=max(dp1[j]+1,dp1[i]);
    memset(dp2,0,sizeof(dp2));
    for (int i=n;i>=1;i--)
        for (int j=n+1;j>i;j--)
            if (t[i]>t[j])
                dp2[i]=max(dp2[j]+1,dp2[i]);
    ans=0;
    for (int i=1;i<=n;i++)
        ans=max(ans,dp1[i]+dp2[i]-1);
    printf("%d",n-ans);
    return 0;
}

动态规划AC

#include<cstring>
#include<iostream>
using namespace std;
int a[200],b[200],c[200];
main()
{
    int n,i,j,maxx;
    cin>>n;
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=n;i++)
    {
        b[i]=1;
        for(j=1;j<=i-1;j++)
        if((a[i]>a[j])&&(b[j]+1>b[i]))
        b[i]=b[j]+1;
    }
    for(i=n;i>=1;i--)
    {
        c[i]=1;
        for(j=i+1;j<=n;j++)
        if((a[j]<a[i])&&(c[j]+1>c[i]))
        c[i]=c[j]+1;
    }
    maxx=0;
    for(i=1;i<=n;i++)
    if(b[i]+c[i]>maxx)
    maxx=b[i]+c[i];
    cout<<n-maxx+1<<endl;
}

#include<iostream>
#include<cstdio>
using namespace std;
int a[105],up[105],down[105],n,ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=n;i++)
{
ans=0;
for (int j=1;j<=i;j++)
if (a[j]<a[i])
ans=max(ans,up[j]);
up[i]=ans+1;
}
for (int i=n;i>=1;i--)
{
ans=0;
for (int j=n;j>=i;j--)
if (a[j]<a[i])
ans=max(ans,down[j]);
down[i]=ans+1;
}
for (int i=1;i<=n;i++)
ans=max(ans,up[i]+down[i]);
printf("%d",n-ans+1);
return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int n,a[101],f[101],g[101],ans=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=g[i]=1;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=i-1;j++)
if (a[i]>a[j])
f[i]=max(f[i],f[j]+1);
for (int i=n;i>=1;i--)
for (int j=n;j>=i+1;j--)
if (a[i]>a[j])
g[i]=max(g[i],g[j]+1);
for (int i=1;i<=n;i++)
ans=max(ans,f[i]+g[i]-1);
printf("%d\n",n-ans);
}

```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[110],s[110],n[110],z[101];
int main()
{
    int p,i,k;
    cin>>p;
    for(i=1;i<=p;i++)
    cin>>a[i];
    for(i=1;i<=p;i++)
     for(k=1;k<i;k++)
      if(a[i]>a[k])
       if(s[i]<=s[k])
        s[i]=s[k]+1;
    for(i=p;i>=1;i--)
     for(k=p;k>i;k--)
      if(a[i]>a[k])
       if(n[i]<=n[k])
       n[i]=n[k]+1;
    for(i=1;i<=p;i++)
    z[i]=s[i]+n[i];
    sort(z+1,z+p+1);
    cout<<p-z[p]-1;
    return 0;
}

#include <stdio.h>
#include <string.h>
int hei[101],ldp[101],rdp[101];
int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
if(n==-1) break;
int i;
memset(ldp,0,sizeof(ldp));
for (i=1;i<=n;i++)
{
scanf("%d",&hei[i]);

ldp[i]=1;
}
int j;
for (i=1;i<=n;i++)
{
for (j=i-1;j>=0;j--)
{
if (hei[j]<hei[i]&&ldp[i]<ldp[j]+1)
{
ldp[i]=ldp[j]+1;
}
}
}
memset(rdp,0,sizeof(rdp));
for (i=1;i<=n;i++)
{
rdp[i]=1;
}

for (i=n;i>=1;i--)
{
for (j=i+1;j<=n;j++)
{
if (hei[j]<hei[i]&&rdp[i]<rdp[j]+1)
{
rdp[i]=rdp[j]+1;
}
}
}
int max=0;
for (i=1;i<=n;i++)
{
if (rdp[i]+ldp[i]>max)
{
max=rdp[i]+ldp[i];
}
}
max--;

printf("%d\n",n-max);
}
return 0;
}

#include <stdio.h>
#include <string.h>
int hei[101],ldp[101],rdp[101];
int main()
{
int n;
while (scanf("%d",&n)!=EOF)
{
if(n==-1) break;
int i;
memset(ldp,0,sizeof(ldp));
for (i=1;i<=n;i++)
{
scanf("%d",&hei[i]);

ldp[i]=1;
}
int j;
for (i=1;i<=n;i++)
{
for (j=i-1;j>=0;j--)
{
if (hei[j]<hei[i]&&ldp[i]<ldp[j]+1)
{
ldp[i]=ldp[j]+1;
}
}
}
memset(rdp,0,sizeof(rdp));
for (i=1;i<=n;i++)
{
rdp[i]=1;
}

for (i=n;i>=1;i--)
{
for (j=i+1;j<=n;j++)
{
if (hei[j]<hei[i]&&rdp[i]<rdp[j]+1)
{
rdp[i]=rdp[j]+1;
}
}
}
int max=0;
for (i=1;i<=n;i++)
{
if (rdp[i]+ldp[i]>max)
{
max=rdp[i]+ldp[i];
}
}
max--;

printf("%d\n",n-max);
}
return 0;
}

/*
超经典的双向LIS~
我们可以考虑到
我们求解LIS是定义f[i]表示前i个人的最长LIS
那么我们实际要求的是一个正向LIS拼上一个反向LIS的最大值
这个题目的核心就是选取一个中间人
那个转折点
所以我们可以枚举这个中间人
然后看哪个人作为中间人最优QAQ
首先想法是枚举中间人位置，然后左右求LIS，O(N^3)对于n<101的数据可过。
考虑到中间人不受LIS的影响，故只需正反两遍LIS，再枚举中间人位置，可降为
O(N^2)
所以我们从前向后先做一次正向LIS
求出所有的前i个人的最大LIS
然后从后向前做一次LIS(从前向后做最长下降也可以)
注意求出来之后i一定要在序列中
然后就可以得出所有的f1[i],f2[i]
其中f1[i]表示正向的前i个人的LIS
f2[i]表示反向的前i个人的LIS
那么我们就枚举所有中间点
选取最大的f1[i]+f2[i]即可
注意到因为这样会算重复中间那个人
所以-1就好了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int a[105];
int f1[105];
int f2[105];
int n;
int ans;

void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f1[i]=f2[i]=1;
    }
}

void LIS()
{
    for(int i=2;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[i]>a[j])
                f1[i]=max(f1[i],f1[j]+1);
    for(int i=n-1;i>=1;i--)
        for(int j=n;j>i;j--)
            if(a[i]>a[j])
                f2[i]=max(f2[i],f2[j]+1);
}

void out()
{
    for(int i=1;i<=n;i++)
        ans=max(ans,f1[i]+f2[i]-1);
    printf("%d\n",n-ans);
}

int main()
{
    init();
    LIS();  
    out();
}
     

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 110;
int student[maxn];
int a_rank[maxn];
int d_rank[maxn];
vector <int> length;

int cal_ascending(int start,int end){
memset(a_rank,0,sizeof(a_rank));
for(int i = end;i >= start;i--){
for(int p = i + 1;p <= end;p++){
if(student[i] < student[p]) a_rank[i] = max(a_rank[p],a_rank[i]);
}
a_rank[i]++;
}
int leng = 0;
for(int i = start;i <= end;i++){
leng = max(leng,a_rank[i]);
}
return leng;
}

int cal_descending(int start,int end){
memset(d_rank,0,sizeof(d_rank));
for(int i = start;i <= end;i++){
for(int p = start;p < i;p++){
if(student[i] < student[p]) d_rank[i] = max(d_rank[p],d_rank[i]);
}
d_rank[i]++;
}
int leng = 0;
for(int i = start;i <= end;i++){
leng = max(leng,d_rank[i]);
}
return leng;
}

int main(){
int n;
cin >> n;
int check = n;
int num = 1;
while(check--){
cin >> student[num++];
}
int a_len,d_len,all_len;
for(int i =1;i <= n;i++){
a_len = cal_ascending(1,i);
d_len = cal_descending(i,n);
all_len = a_len + d_len - 1;
length.push_back(all_len);
}
int ans = 0;
for(int i = 0;i < length.size();i++) ans = max(ans , length[i]);
cout << n - ans;
}

O(nlogn)

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[1010], n, h[1010], tmp[1010];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
memset(tmp, 0x3f3f3f3f, sizeof(tmp));
for (int i = 1; i <= n; i++) {
*lower_bound(tmp, tmp + n, h[i]) = h[i];
dp[i] += lower_bound(tmp, tmp + n, inf) - tmp;
}
reverse(h + 1, h + 1 + n);
memset(tmp, 0x3f3f3f3f, sizeof(tmp));
for (int i = 1; i <= n; i++) {
*lower_bound(tmp, tmp + n, h[i]) = h[i];
dp[n - i + 1] += lower_bound(tmp, tmp + n, inf) - tmp;
}
int maxans = 0;
for (int i = 1; i <= n; i++) {
maxans = max(maxans, dp[i] - 1);
}
cout << n - maxans;
return 0;
}


虽然很不想承认，但还是要说，一定，一定要看清是出列的人数（看错竟然有30分）
果断两遍LIS，至于为什么要发，因为没人用二（hua）分（ji）啊

#include<bits/stdc++.h>
using namespace std;

const int up=100+5;
int a1[up],a2[up],f1[up],f2[up],g[up];

int main()
{
    int n,k,maxn=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a1[i]);
        a2[n-i+1]=a1[i];
    }
    memset(g,0x7f,sizeof g);
    for(int i=1;i<=n;i++)
    {
        k=lower_bound(g+1,g+n+1,a1[i])-g;
        f1[i]=k;
        g[k]=a1[i];
    }
    memset(g,0x7f,sizeof g);
    for(int i=1;i<=n;i++)
    {
        k=lower_bound(g+1,g+n+1,a2[i])-g;
        f2[n-i+1]=k;
        g[k]=a2[i];
    }
    for(int i=1;i<=n;i++) maxn=max(maxn,f1[i]+f2[i]);
    printf("%d\n",n+1-maxn);
}

正着一遍最长上升子序列 反着一遍

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,ans=0;
vector<int> v(1,0),v1(1004,1),v2(1004,1);
int main(){
cin>>n;
for(int i=1,a;i<=n;i++){
cin>>a;
v.push_back(a);
}
for(int i=2;i<=n;i++)
for(int j=1;j<i;j++)
if(v[j]<v[i]&&v1[j]+1>v1[i])
v1[i]=v1[i]+1;
for(int i=n-1;i>0;i--)
for(int j=i+1;j<=n;j++)
if(v[j]<v[i]&&v2[j]+1>v2[i])
v2[i]=v2[j]+1;
for(int i=1;i<=n;i++)
ans=max(ans,v2[i]+v1[i]-1);
cout<<n-ans<<endl;
return 0;
}


#include<iostream>
using namespace std;

int max(int x, int y)
{
if (x > y) { return x; }
else { return y; }
}
void lis(int i)
{
const int length = 120;
int a[length], d_up[length], d_down[length];
for (int j = 1; j <= i; j++)
{
cin >> a[j]; d_up[j] = 1; d_down[j] = 1;

}
for (int j = 2; j <= i; j++)
{
for (int k = 1; k <= j - 1; k++)
{
if (a[j] <= a[k]) { continue; }
d_up[j] = max(d_up[j], d_up[k] + 1);
}
}
for (int j = i - 1; j >= 1; j--)
{
for (int k = i; k >= j + 1; k--)
{
if (a[j] <= a[k]) { continue; }
d_down[j] = max(d_down[j], d_down[k] + 1);
}
}
for (int j = 1; j <= i; j++)
{
d_up[j] = d_up[j] + d_down[j];
}
int maxx = 0;
for (int j = 1; j <= i; j++)
{
maxx = max(maxx, d_up[j]);
}
maxx = maxx - 1;

cout << i - maxx << endl;
}

int main()
{
int i;
cin >> i;
lis(i);
return 0;
}

第一次直接输出留下人的个数了（就是直接输出ans）.....
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define dwn(i, x, y) for (int i = x; i >= y; --i)

using namespace std;

int n, t[128];
int f[128], g[128];
int main(int argc, const char *argv[]) {
scanf("%d", &n);
rep(i, 1, n) {
scanf("%d", &t[i]);
}
rep(i, 1, n) {
f[i] = 1;
rep(j, 1, i - 1) {
if (t[j] < t[i]) f[i] = max(f[i], f[j] + 1);
}
}
dwn(i, n, 1) {
g[i] = 1;
rep(j, i + 1, n) {
if (t[i] > t[j]) g[i] = max(g[i], g[j] + 1);
}
}
int ans = 0;
rep(i, 1, n) {
ans = max(ans, f[i] + g[i] - 1);
}
printf("%d\n", n - ans);
return 0;
}

本题最快用单调队列优化LIS时间复杂度为O（nlog 2 n） 不过这题数据似乎朴素算法O（n3）也是秒杀的

uses math;
var
 n,i,j,ans:longint;
 a,f,f2:array[1..1000]of longint;
begin
 ans:=0;
 n:=0;
 readln(n);
 for i:=1 to n do read(a[i]);
 for i:=1 to n do begin
  f[i]:=1;
  f2[i]:=1;
 end;
 for i:=2 to n do
  for j:=1 to i-1 do 
   if (a[j]<a[i])and(f[j]+1>f[i]) then f[i]:=f[j]+1;
 
 
 
 for i:=n-1 downto 1 do
  for j:=n downto i+1 do 
   if (a[j]<a[i])and(f2[j]+1>f2[i]) then f2[i]:=f2[j]+1;
 
 for i:=1 to n do 
  for j:=i+1 to n do 
 if f[i]<>f2[j] then ans:=max(ans,f[i]+f2[j]);
 
 for i:=1 to n do ans:=max(ans,max(f[i],f2[i]));
 writeln(n-ans);
end.

首先想法是枚举中间人位置，然后左右求LIS，O(N^3)对于n<101的数据可过。
考虑到中间人不受LIS的影响，故只需正反两遍LIS，再枚举中间人位置，可降为

O(N^2)。
```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 105;
int n,res = 0,A[N],lis1[N],lis2[N];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",&A[i]);
memset(lis1,0,sizeof(lis1));
memset(lis2,0,sizeof(lis2));
lis1[1] = lis2[n] = 1;
for(int i = 2;i <= n;i++)//lis1[i]表示在前i个数中，包括第i个数

所构成的最长上升子序列长度
{
for(int j = 1;j < i;j++)
if(A[i] > A[j]) lis1[i] = max(lis1[i],lis1[j]);
lis1[i]++;
}
for(int i = n - 1;i >= 1;i--)//lis2[i]表示在后i个数中，包括第i

个数所构成的最长下降子序列长度
{
for(int j = n;j > i;j--)
if(A[i] > A[j]) lis2[i] = max(lis2[i],lis2[j]);
lis2[i]++;
}
for(int i = 1;i <= n;i++)
res = max(res,lis1[i] + lis2[i] - 1);
printf("%d\n",n - res);
return 0;

}
```
还可利用lis的值进行分类后数据的单调性进行二分查找，可降为O(nlogn)。
//不过此题根本没必要，O(n^2)的复杂度time已经为0了。。。

#include <cstdio>

int main(){
//  freopen("in.txt","r",stdin);
    int n,a[500];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int f1[500],f2[500];
    for(int i=1;i<=n;i++)
        f1[i]=1,f2[i]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i-1;j++){
            if(a[i]>a[j]&&f1[i]<f1[j]+1)
                f1[i]=f1[j]+1;
        }
    for(int i=n-1;i>=1;i--)
        for(int j=n;j>=i+1;j--){
            if(a[i]>a[j]&&f2[i]<f2[j]+1)
                f2[i]=f2[j]+1;
        }
    int f[500],min=99999;
    for(int i=1;i<=n;i++)
        f[i]=i-f1[i]+n-i+1-f2[i];
        
    for(int i=1;i<=n;i++)
        min=f[i]<min?f[i]:min;
    printf("%d",min);
    return 0;
}

明明可以用O(nlogn)的时间复杂度解决，数据却这么小
附上程序O(nlogn)的代码：
#include<iostream>
#include<cstdio>
int left[101],right[101],f[101],h[101],len,n,l,r,mid,t,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&h[i]);
f[1]=h[1];left[1]=1;len=1;
for(int i=2;i<=n;++i)
{
for(t=0,l=1,r=len,mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
if(f[mid]<h[i]) l=mid+1,t=mid;else r=mid-1;
if(++t>len) f[++len]=h[i];
else if(f[t]>h[i]) f[t]=h[i];
left[i]=len;
}
f[1]=h[n];right[n]=1;len=1;
for(int i=n-1;i;--i)
{
for(t=0,l=1,r=len,mid=(l+r)>>1;l<=r;mid=(l+r)>>1)
if(f[mid]<h[i]) l=mid+1,t=mid;else r=mid-1;
if(++t>len) f[++len]=h[i];
else if(f[t]>h[i]) f[t]=h[i];
right[i]=len;
}
for(int i=2;i<=n;++i)
ans=std::max(ans,left[i-1]+right[i]);
printf("%d\n",n-ans);
return 0;
}

灰常简单^>_<^
c
#include<stdio.h>
int s[101],f[101],g[101];
int n;
void max(int& a,int b){ if(a<b)a=b; }
int main(){
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",s+i);
f[i]=g[i]=1;
}
for(int i=1;i<n;++i)
for(int j=0;j<i;++j)
if(s[i]>s[j]) max(f[i],f[j]+1);
for(int i=n-2;~i;--i)
for(int j=n-1;j>i;--j)
if(s[i]>s[j]) max(g[i],g[j]+1);
int ans=0;
for(int i=0;i<n;++i) max(ans,f[i]+g[i]);
printf("%d",n-ans+1);
}