补了一道蓝。

prediction

2026-06-20 21:36:32

发布于：浙江

8阅读

0回复

0点赞

上次P1012 [NOIP 1998 提高组] 拼数被降绿了，由于我不会做 perm ，于是把P4170 [CQOI2007] 涂色写掉了。

区间 dp 。我们不难发现一块木板时绝对要用 $1$ 次来涂，当然也是最小的次数，所以初始化为 $1$ 。（一块板子的）

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()];
}