Luogu3847 [TJOI2007]调整队形

发布于 2019-10-30  228 次阅读


Link

这类区间DP的要点就是不要被它一堆操作搞晕了

首先可以设 f[l][r] 表示将 [l,r] 这段区间搞成回文的最少操作步数。

不妨分析一波它的操作:

1、在队伍左或右边加一个人(衣服颜色依要求而定);

2、在队伍中任两个人中间插入一个人(衣服颜色依要求而定);

这两个操作都可以被替换为第三种操作:

3、剔掉一个人;

此时 l,r 位置上的颜色有两种关系:

  1. $a[l] = a[r]$
  2. $a[l] ≠ a[r]$

如果是第一种,那么无需操作,f[l][r] 应该等于l位置和r位置还没确定时的步数,即

$f[l][r] = f[l+1][r+1]$

若是第二种情况,在l的左边(即l-1)的位置加一个与j颜色相同的人实质上跟删除第j个人是等价的,同理,在r右边加上一个与i颜色相同的人跟删掉i是等价的,所以:

$f[l][r] = min(f[i+1][j-1],f[i+1][j],f[i][j-1]) + 1$

上代码

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

const int SIZE = 3000 + 5;

int n;
int a[SIZE], f[SIZE][SIZE];

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

int main()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (a[l] == a[r]) f[l][r] = f[l + 1][r - 1];
            else f[l][r] = std::min(f[l + 1][r], std::min(f[l][r - 1], f[l + 1][r - 1])) + 1;
        }
    printf("%d", f[1][n]);
    return 0;
}

朴实沉毅