P1091 合唱队形

  • 求N-K的最小值，转换为求k的最大值
  • 与登山类似

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)

const int N = 1010;

int t,n;
int a[N];
int f[N],g[N];

int main() {
    cin >> n;
    mm(a,0);mm(f,0);mm(g,0);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) {
        f[i] = 1;
        for(int j = 1; j < i; j ++ ) {
            if(a[j] < a[i]) {
                f[i] = max(f[i],f[j] + 1);
            }
        }
    }
    for(int i = n; i; i -- ) {
        g[i] = 1;
        for(int j = n; j > i; j -- ) {
            if(a[j] < a[i]) {
                g[i] = max(g[i],g[j] + 1);
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++ ) res = max(res,f[i] + g[i] - 1);
    cout<<n - res<<endl;
    return 0;
}