补了一道蓝。
2026-06-20 21:36:32
发布于：浙江
17阅读
0回复
0点赞
上次P1012 [NOIP 1998 提高组] 拼数被降绿了，由于我不会做 perm ，于是把P4170 [CQOI2007] 涂色写掉了。
区间 dp 。我们不难发现一块木板时绝对要用次来涂，当然也是最小的次数，所以初始化为。（一块板子的）
for(int i = 1;i<=a.length();i++) dp[i][i]=1;
在剩下的多块板子里面每一个区间都取最小值，最后 dp[1][a.length()] 就是一整块的答案。
cout<<dp[1][a.length()];
每一个区间看看是不是能偷懒，也就是一次涂完，注意一次涂掉左右端点的次数是不会比分别去涂多的，所以我们只要看左边区间与右边区间哪个小就行（因为每个区间的左/右端点都可以在涂另一个端点的时候顺带过去）
if(x[l]==x[r])//一起涂色
{
dp[l][r]=min(dp[l+1][r],dp[l][r-1]);
}
如果不是同色块那就在区间里找分割点去最小值，这个就是区间 dp 的核心思想了（其实我也不太清楚啊）
for(int k = l;k<r;k++)//枚举分割点
{
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
}
AC CODE
#include <iostream>
using namespace std;
int dp[55][55];
const int INF=0x3f3f3f3f;//极大值代表不知道的区间最小值，便于取最小值
int main()
{
string a;
cin>>a;
string x=" "+a;//空格省掉0（其实是我太拉了不会判边界）
for(int i = 1;i<=a.length();i++) dp[i][i]=1;//初始化
for(int i = 2;i<=a.length();i++)
{
for(int l = 1;l+i-1<=a.length();l++)
{
int r=l+i-1;
dp[l][r]=INF;
if(x[l]==x[r])//一起涂色
{
dp[l][r]=min(dp[l+1][r],dp[l][r-1]);
}
for(int k = l;k<r;k++)//枚举分割点
{
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
}
}
}
cout<<dp[1][a.length()];
}
这道是区间 dp 的好题，也是我的第道蓝，在此纪念一下吧。（因为第一个是我爆搜拿数据打表的）
后记
羡慕 sk 能和帅童和 Lost 打比赛。
我菜菜。
有帮助，赞一个