洛谷P1091 合唱队形

两趟最长上升子序列dp,枚举中间的人求队伍长度最大值,然后总人数减去它就行了.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int n;
int a[105];
int dp1[105];
int dp2[105];
int ans;
int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    dp1[i]=1;
    for (int k = 1; k < i; ++k) {
      if (a[k] < a[i]) {
        dp1[i] = max(dp1[k] + 1, dp1[i]);
      }
    }
  }
  for (int j = n; j >= 1; --j) {
    dp2[j]=1;
    for (int k = n; k >= j; --k) {
      if (a[k] < a[j]) {
        dp2[j] = max(dp2[k] + 1, dp2[j]);
      }
    }
  }
  for(int i=1;i<=n;++i){
      ans=max(ans,dp1[i]+dp2[i]-1);
  }
  cout << n-ans << endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}