[Luogu] P4170 [CQOI2007]涂色 区间dp

前言

传送门 : https://www.luogu.com.cn/problem/P4170 做的时候, 这是区间DP ？ 做完的时候,这的确是区间DP

思路

石子合并中 : f [ i ] [ j ] f[i][j] f[i][j]表示从第 i i i堆合并到第 j j j堆的最小方案

同理 : 本题可以 表示 s [ i ] 到 s [ j ] s[i]到s[j] s[i]到s[j]的最小染色次数

考虑状态转移 :

( i = = j ) 时 , f [ i ] [ i ] = 1 (i==j)时,f[i][i] = 1 (i==j)时,f[i][i]=1 ( i ! = j , S [ i ] = = S [ j ] ) 时 , f [ i ] [ j ] = m i n ( f [ i − 1 ] [ j ] , f [ i ] [ j + 1 ] ) 比 上 一 次 涂 色 + 1 (i!=j,S[i]==S[j])时,f[i][j] =min(f[i-1][j],f[i][j+1]) 比上一次涂色+1 (i!=j,S[i]==S[j])时,f[i][j]=min(f[i−1][j],f[i][j+1])比上一次涂色+1 ( i ! = j , S [ i ] ! = S [ j ] ) 时 , f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] ) 分 层 两 个 区 间 , 枚 举 断 点 (i!=j,S[i]!=S[j])时,f[i][j] =min(f[i][j],f[i][k]+f[k+1][j])分层两个区间,枚举断点 (i!=j,S[i]!=S[j])时,f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])分层两个区间,枚举断点

CODE

#include 
using namespace std;
const int N  = 60;
int  f[N][N],n;

void solve()
{
    string s;cin>>s;
    s = " "+s;
    int n  = s.size();
    n--;

    memset(f,0x3f,sizeof f);

    for(int i=1;i