则他们的身高满意T1&lt,老师愿意将合唱队调整得符合供给

P3847 [TJOI2007]调动队形

P1091 合唱队形

难点背景

全校艺术节上,规定合唱队要列席比赛,各种队员的衣服颜色不能够很混乱:合唱队员应排成一排行,且衣裳颜色必须是反正对称的。

譬如:“红深灰蓝蓝红”或“红紫铜色紫红红”都以适合的,而“红浅绛红红”或“深紫蓝红”就不符合必要。

合唱队人数自然很多,仅现有的同窗就大概会有3000个。老师希望将合唱队调整得符合供给,但想要调整尽量少,减弱麻烦。以下任一动作认为是三回调整:

难点叙述

N位同学站成一排,音乐导师要请里面的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。

合唱队形是指那样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,
则他们的身高满足T1<…<Ti>Ti+1>…>TK(1<=i<=K)。

你的天职是,已知全数N位同学的身高,总计最少要求二个人同学出列,能够使得剩下的同室排成合唱队形。

标题叙述

壹 、在军队左或左边加壹个人(衣裳颜色依需求而定);

贰 、在军事中任多个人个中插入一人(衣裳颜色依须要而定);

叁 、剔掉一人;

肆 、让1位换服装颜色;

教师想精通就当前的队形最少的调动次数是多少,请你编2个主次来解惑他。

因为加盟合唱队很走俏,你能够认为人数是极致的,即随时想加壹位都能找到人。同时衣裳颜色也是随机的。

输入输出格式

输入格式:

 

输入文件chorus.in的首先行是二个整数N(2<=N<=100),表示同学的总额。第三行有n个整数,用空格分隔,第i个整数Ti(130<=Ti<=230)是第i位同学的身高(毫米)。

 

输出格式:

 

输出文件chorus.out包涵一行,这一行只含有多少个整数,正是起码要求几个人同学出列。

 

输入输出格式

输入格式:

 

第③行是三个整数n(1<=n<=三千)。

第①行是n个整数,从左到右分别表示现有的每一种队员衣裳的颜料号,都是1到3000的整数。

澳门真人网上娱乐网址, 

出口格式:

 

多少个数,即对于输入队列,要调整得符合供给,最少的调动次数。

 

输入输出样例

输入样例#1:

8
186 186 150 200 160 130 197 220

出口样例#1:

4

输入输出样例

输入样例#1:

5
1 2 2 4 3

出口样例#1:

2

/*
    操作一共有四种,但是我们本着简化的原则可以发现 操作1,2 即往数列里加数可以等效的被一步操作3 即删掉 你想加数对应的那个数来代替,所以无非就两种操作:1.改变一个数。2.删掉一个数。求最少经过几步操作可以使原数列变为回文的 
    我们考虑dp[i][j]表示把i…j变成回文所需的最小步数,则如果 
    a[i]==a[j] 则dp[i][j]=dp[i+1][j-1] 
    else 
    dp[i][j]=dp[i+1][j-1]+1 改变一个数 
    dp[i][j]=dp[i+1][j]+1 删掉a[i] 
    dp[i][j]=dp[i][j-1]+1 删掉a[j] 
    取最小值即可。复杂度O(n2)
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 3010
int dp[maxn][maxn],n,a[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            if(a[i]==a[j])dp[i][j]=dp[i+1][j-1];
            else dp[i][j]=min(min(dp[i+1][j-1],dp[i+1][j]),dp[i][j-1])+1;
        }
    }
    printf("%d",dp[1][n]);
}

 

说明

对于50%的数据,保证有n<=20;

对此任何的多少,保障有n<=100。

/*
    正着倒着分别做一遍最长上升子序列
    然后枚举最高点
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 110
using namespace std;
int n,a[maxn],f1[maxn],f2[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f1[i]=f2[i]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(a[j]<a[i])f1[i]=max(f1[i],f1[j]+1);
    for(int i=n;i>=1;i--)
        for(int j=n;j>=i;j--)
            if(a[j]<a[i])f2[i]=max(f2[i],f2[j]+1);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f1[i]+f2[i]-1);
    printf("%d",n-ans);
}