洛谷4170 [CQOI2007]涂色

题解 动态规划 动态规划-区间DP 提高+/省选-
题目链接 编辑文章

题意

给一个长度为 $N$ 的木板染色,木板有初始颜色,要求染成一种颜色。每次可以选择一段连续的格子染色,颜色可以被覆盖。求至少要染多少次。

$N\le 50$ 。

题解

用 $f[l][r]$ 表示将 $[l,r]$ 染成一种颜色的最少次数。

当 $S_l=S_r$ 时,可以在染一边时顺便把另一边染了,即 $f[l][r]=\min(f[l+1][r],f[l][r-1])$ 。

否则可以枚举中间点 $k$ ,$f[l][r]=\min_{k=l}^{r-1} f[l][k]+f[k+1][r]$ 。

当 $l=r$ 时,初值为 $1$ 。

我还是写的记搜。

#include<bits/stdc++.h>

using namespace std;

char s[55];
int n,f[55][55];

int dfs(int l,int r)
{
    if (l==r) return 1;
    int &ans=f[l][r];
    if (ans) return ans;
    if (s[l]==s[r]) return ans=min(dfs(l+1,r),dfs(l,r-1));
    ans=1e9;
    for (int k=l;k<r;k++) ans=min(ans,dfs(l,k)+dfs(k+1,r));
    return ans;
}

signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    return !printf("%d",dfs(1,n));
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空