【题解】luogu 1091【合唱队形】

分析

题意很明显,$T_i$前是上升序列,$T_i$后是下降序列。
答案就是求$\max${最长上升序列$+$最长下降序列}。

代码

#include<cstdio>

const int MAXN = 100 + 6;
int h[MAXN],dp1[MAXN],dp2[MAXN];

inline int max(int a,int b){return a > b ? a : b;}

int main(){
    int n,ans = 1;scanf("%d",&n);
    for(int i = 0;i < n;i++) scanf("%d",&h[i]);
    for(int i = 0;i < n;i++) for(int j = 0;j < i;j++) if(h[j] < h[i]) dp1[i] = max(dp1[i],dp1[j] + 1);
    for(int i = n - 1;i >= 0;i--) for(int j = n;j > i;j--) if(h[i] > h[j]) dp2[i] = max(dp2[i],dp2[j] + 1);
    for(int i = 0;i < n;i++) ans = max(ans,dp1[i] + dp2[i] - 1);
    printf("%d",n - ans - 1);

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注