洛谷P3847 [TJOI2007]调整队形

题目背景

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

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

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

题目描述

1、在队伍左或右边加一个人（衣服颜色依要求而定）；

2、在队伍中任两个人中间插入一个人（衣服颜色依要求而定）；

3、剔掉一个人；

4、让一个人换衣服颜色；

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

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

输入输出格式

输入格式：

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

第二行是n个整数，从左到右分别表示现有的每个队员衣服的颜色号，都是1到3000的整数。

输出格式：

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

输入输出样例

输入样例#1：复制

5
1 2 2 4 3

输出样例#1：复制

发现自己不是很会区间DP。

现在想一下发现其实区间dp解决的是一些记录前缀状态不好做的题目。转移的关键自然也在于从小的区间到大的区间的方案。这道题就可以记f(l,r)表示令区间l,r合法的最小代价。

发现由一个合法状态一定可以由另一个合法状态操作出(空区间自然合法)。只要每一次对当前区间两端字符的来源讨论一下，代入题目描述的四种情况即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 3e3 + 5;
int dp[maxn][maxn], n, num[maxn], L, R;

int main() {
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    for(register int l = 1; l <= n; ++l)
        scanf("%d", &num[l]), dp[l][l] = 0;
    for(register int l = 1; l < n; ++l)
        dp[l + 1][l] = 0;
    for(register int l = 2; l <= n; ++l)
        for(register int i = 1; i + l - 1 <= n; ++i) {
            L = i, R = i + l - 1;
            if(num[L] == num[R]) dp[L][R] = min(dp[L][R], dp[L + 1][R - 1]);
            else dp[L][R] = min(dp[L][R], dp[L + 1][R - 1] + 1);
            dp[L][R] = min(dp[L][R], dp[L][R - 1] + 1);
            dp[L][R] = min(dp[L][R], dp[L + 1][R] + 1);
            //dp[L][R] = 
        }
    printf("%d", dp[1][n]);
    return 0;
}

Rockdu's Blog