【每日一题】 [CQOI2007]涂色PAINT

题意：
对于一段空白的木板，每次可以选取连续的一段涂上任意中颜色，问将木板涂至给定颜色需要的最少次数。

思路:
区间dp。
原问题：将木板全部涂色完成需要的最少次数。
子问题：将木板的连续某一段涂完需要的最少次数。
记：dp[i][j]表示将木板的第i块至第j块涂成指定颜色需要的最少次数。

区间dp考虑先枚举长度；
当块的长度为一时，只要涂一次，即dp[i][i]=1；
当木板长度大于一时：
若端点的两块颜色相同，可认为在涂一端时顺带涂了另一端，所以 dp[i][j]=min(dp[i][j-1],d[i+1][j])；
若端点的两块颜色不相同，则可以在端点间枚举端点，即先涂第i块到第k块，再涂第k+1块到第j块，所以 dp[i][j]=min{dp[i][k]+dp[k+1][j]}(i<k<j);

最后输出第一块到最后一块的次数即可。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=2e5+9;
const ll maxx=1e12+9;

string s;
int dp[555][555];

int main()
{
    cin>>s;
    int n=s.size();
    for(int i=0;i<n;i++) dp[i][i]=1;
    for(int len=2;len<=n;len++)
    {
        for(int i=0,j=i+len-1;j<n;i++,j++)
        {
            if(s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
            else
            {
                dp[i][j]=dp[i][i]+dp[i+1][j];
                for(int k=i+1;k<j;k++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
    }
    printf("%d\n",dp[0][n-1]);
}