题解 | #合唱队形#

合唱队形链接

/* 顺着0->i计算以i结尾的最大递增子序列长,逆着计算n-1->i的以i结尾的最大递增序列长,遍历0->n-1寻找最小的二者和-1 */

#include <algorithm>
#include <iostream>
#include <cstdio>
 
using namespace std;
const int maxn = 300;
 
int main(){
    int n;
    while(~scanf("%d", &n)){
        int dp1[maxn];//左边最大升序子序列的长度
        int dp2[maxn];//右边最长降序子序列的长度
        int A[maxn];       
        for(int i = 0; i < n; i++){
            scanf("%d", &A[i]);//输入
        }
 
        /*从前往后寻找以i点为尾的最长递增子列*/
        for(int i = 0; i < n; i++){
            dp1[i] = 1;/*每点为尾的子列长度最小都为1*/
            for(int j = 0; j < i; j++){
                if(A[j] < A[i]){
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }  
        }
 
        /*从后往前寻找以i点为尾的最长递增子列*/
        for(int i = n - 1; i >= 0; i--){
            dp2[i] = 1;/*每点为尾的子列长度最小都为1*/
            for(int j = n - 1; j > i; j--){
                if(A[j] < A[i]){
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }
 
        int ans = 1;
        /*寻找点i两个子列和的最大值*/
        for(int i = 0; i < n; i++){
            if(dp1[i] + dp2[i] > ans){
                ans = dp1[i] + dp2[i];
            }
        }
        printf("%d\n", n - ans + 1);//重复减了自身两次,故加1
 
    }
    return 0;
}
全部评论

相关推荐

ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
一条从:又想干活还想拿工资,什么好事都让你占了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务