SSL 2674_覆盖_dp

发布于 2017-08-09  3550 次阅读

题目描述

现在小B拿到了一条长度为n的木块，初始时上面什么颜色都没有。为了美观，现在小B希望把它的n个单位长度分别涂上红、绿、蓝三种颜色，每种颜色可以用一个大写字母表示，分别是：RGB。作为一个不合格的油漆工，每次你可以把一段连续的木版涂成随意一种颜色，但是你发现，后涂的颜色会覆盖先涂的颜色。为了方便，请你用尽量少的涂色次数达到目标。

 

思路

此题是区间处理

设f[i][j] 表示i到j的区间处理好的最小次数

显然有f[i][i]=1 如果s[i] == s[j] $f[i][j] = min(f[i+1][j],f[i][j-1],f[i+1][j-1]+1)$

即多涂一段或使另一端扩展一位

否则可以枚举一个k $f[i][j] = min(f[i][k] + f[k + 1][j])$

#include 
#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define maxn 61
#define INF 0x3f3f3f3f
#define min(x, y) (x) < (y) ? (x) : (y)
int f[maxn][maxn]; 
char ch[maxn];
int main()
{
    cin >> ch;
    fill(f, INF);
    int n = strlen(ch);
    for (int i = 0; i < n; i++)
        f[i][i] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < n - 1; j++)
        {
            int k = j + i - 1;
            if (k > n) continue;
            if (ch[j] == ch[k])
                f[j][k] = min(min(f[j + 1][k], f[j][k - 1]), f[j + 1][k - 1] + 1);
            else
            {
                for (int l = j; l < k; l++)
                    f[j][k] = min(f[j][k], f[j][l] + f[l + 1][k]);
            }
        }
    printf("%d\n", f[0][n - 1]);
}

 

]]>