银河88元彩金短信洛谷P3847 [TJOI2007]调整队形

P3847 [TJOI2007]调动队形

题材背景

学校艺术节上,规定合唱队要到位比赛,各个队员的行头颜色不可知很烂:合唱队员应解除成一排名,且衣服颜色要是横针对性如之。

像:“红蓝绿蓝红”或“红蓝绿绿蓝红”都是副的,而“红蓝绿红”或“蓝绿蓝红”就无符合要求。

合唱队人数自然很多,仅现有的同校即使可能会见有3000独。老师愿意用合唱队调整得符合要求,但想如果调整尽量少,减少麻烦。以下无一动作看是一模一样不行调整:

问题叙述

1、在军事左或右手边加一个人(衣服颜色仍要求如肯定);

2、在部队被无两只人当中插一个人数(衣服颜色仍要求要迟早);

3、剔掉一个人;

4、让一个口换衣颜色;

导师想清楚就现阶段的队形最少的调动次数是略,请您造一个次来答复他。

坐在合唱队很紧俏,你得当人是极致的,即随时想加一个人数犹能够找到人。同时装颜色为是自由的。

输入输出格式

输入格式:

 

第一实施是一个整数n(1<=n<=3000)。

次执是n个整数,从左到右分别表示现有的每个队员衣服的颜料号,都是1顶3000之整数。

 

输出格式:

 

一个勤,即对于输入队列,要调得符合要求,最少之调整次数。

 

输入输出样例

输入样例#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]);
}

 

相关文章