M_sea

洛谷3847 [TJOI2007]调整队形
题目描述学校艺术节上,规定合唱队要参加比赛,各个队员的衣服颜色不能很混乱:合唱队员应排成一横排,且衣服颜色必须是左...
扫描右侧二维码阅读全文
27
2018/07

洛谷3847 [TJOI2007]调整队形

题目描述

学校艺术节上,规定合唱队要参加比赛,各个队员的衣服颜色不能很混乱:合唱队员应排成一横排,且衣服颜色必须是左右对称的。

例如:“红蓝绿蓝红”或“红蓝绿绿蓝红”都是符合的,而“红蓝绿红”或“蓝绿蓝红”就不符合要求。

合唱队人数自然很多,仅现有的同学就可能会有3000个。老师希望将合唱队调整得符合要求,但想要调整尽量少,减少麻烦。以下任一动作认为是一次调整:

  1. 在队伍左或右边加一个人(衣服颜色依要求而定);
  2. 在队伍中任两个人中间插入一个人(衣服颜色依要求而定);
  3. 剔掉一个人;
  4. 让一个人换衣服颜色;

老师想知道就目前的队形最少的调整次数是多少,请你编一个程序来回答他。

因为加入合唱队很热门,你可以认为人数是无限的,即随时想加一个人都能找到人。同时衣服颜色也是任意的。

传送门

代码

区间DP。

设$f[i][j]$表示i到j这段区间的最小操作次数。

可以发现,操作1和操作2都可以转换成操作3。
那么只要考虑操作3和操作4即可。

容易得出状态转移方程:

当$a[i]=a[j]$时,$f[i][j]=f[i+1][j-1]$
当$a[i]\neq a[j]$时,$f[i][j]=min(f[i+1][j-1]+1,f[i+1][j]+1,f[i][j-1]+1)$

边界为$f[i][i]=0$,答案为$f[1][n]$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[3010];
int f[3010][3010];

int main() {
    int n=read();
    for (re int i=1;i<=n;i++) a[i]=read();
    for (re int l=2;l<=n;l++)
        for (re int i=1;i+l-1<=n;i++) {
            int j=i+l-1;
            if (a[i]==a[j]) f[i][j]=f[i+1][j-1];
            else f[i][j]=min(min(f[i+1][j],f[i][j-1]),f[i+1][j-1])+1;
        }
    printf("%d\n",f[1][n]);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 50 PM

发表评论