「CQOI2007」「BZOJ1260」涂色paint （区间dp

1260: [CQOI2007]涂色paint

Time Limit: 30 Sec Memory Limit: 64 MB
Submit: 2057 Solved: 1267
[Submit][Status][Discuss]

Description

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。
用尽量少的涂色次数达到目标。

Input

输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

Output

仅一行，包含一个数，即最少的涂色次数。

Sample Input

Sample Output

【样例输入1】
AAAAA

【样例输入1】
RGBGR

【样例输出1】
1

【样例输出1】
3

HINT

40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50

题解

一道区间dp。

设F[L][R]为把[L,R]画完所需的最少次数。初始化F[i][j]=(j-i+1)，表示暴力的一格格涂。

转移时，在[L,R]上枚举两个断点（L',R'），表示在[L,R]上直接覆盖一个区间[L',R']。

一开始让F[L][R]=F[L][L'-1]+F[L'][R']+F[R'+1][R]，表示把大区间视为三个小区间，不在乎他们边界可能有缘。

如果L'上的颜色和L'-1相同，那么可以少画一次；

如果R'上的颜色和R'+1相同，那么可以少画一次；

如果L'-1上的颜色和R'+1上相同，那么又可以少画一次。

最后注意一下，因为假设在[L,R]上涂一层时，就算证明了这一层完全融入背景色，也不可能给原区间一个-1的buff，所以最多只能少画两次。

答案在F[1][n]。

我现在在怀疑是不是只用一个断点就可以解决问题

/**************************************************************

    Problem: 1260

    User: qwerta

    Language: C++

    Result: Accepted

    Time:76 ms

    Memory:1300 kb

****************************************************************/

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

char s[];

int f[][];

int chek(int i,int j)

{

    if(s[i]==s[j])return ;//相同就可以少画一笔

    else return ;

}

int main()

{

    //freopen("a.in","r",stdin);

    cin>>s;

    int n=strlen(s);

    for(int i=n;i;--i)

    s[i]=s[i-];

    for(int i=;i<=n;++i)

    for(int j=i;j<=n;++j)

    f[i][j]=(j-i+);//预处理

    for(int len=;len<=n;++len)

    for(int l=,r=len;r<=n;++l,++r)

    {

        for(int ll=l;ll<=r;++ll)

        for(int rr=ll;rr<=r;++rr)

        {

        int k=f[l][ll-]+f[rr+][r]+f[ll][rr],g=;

        if(ll->=l)g+=chek(ll-,ll);//左边界融入背景(///v///)

        if(rr+<=r)g+=chek(rr,rr+);//右边界融入背景(///v///)

        if(ll->=l&&rr+<=r)g+=chek(ll-,rr+);//左右边界是一样哒！(>w<)

        k-=min(g,);//最多只能少画两笔QAQ

        f[l][r]=min(f[l][r],k);

        }

    }

    cout<<f[][n];

    return ;

}

巴特西