P4170 [CQOI2007] 涂色 区间 dp

P4170 [CQOI2007] 涂色

区间 dp 模板题，不理解为什么是蓝。

将现在考虑的区间 \([l,r]\) 分为 \([l,k]\) 和 \([k+1,r]\)，如果 \(s_l=s_r\) 就可以一起涂，少涂一次。

方程：

\[dp_{l,r}=\min_{k=l}^{r-1} dp_{l,k}+dp_{k+1,r}-[s_l=s_r]

\]

代码：

#include

using namespace std;

char s[60];

int dp[60][60];

int n;

int dfs(int l,int r){

if(dp[l][r])return dp[l][r];

if(l==r)return dp[l][r]=1;

dp[l][r]=114514;

for(int k=l;k

dp[l][r]=min(dp[l][r],dfs(l,k)+dfs(k+1,r)-(s[l]==s[r]));

}

return dp[l][r];

}

int main(){

scanf("%s",s+1);

n=strlen(s+1);

cout<

return 0;

}