洛谷4170 [CQOI2007]涂色

题意

给一个长度为 $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));
}