区间涂色问题

给定一个序列，操作为将一段连续的区间变为相同的颜色，求最少的操作次数。

题1：涂色

P4170 [CQOI2007] 涂色 - 洛谷

假设你有一条长度为 55 的木板，初始时没有涂过任何颜色。你希望把它的 55 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 55 的字符串表示这个目标：RGBGR\texttt{RGBGR}。

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 RRRRR\texttt{RRRRR}，第二次涂成 RGGGR\texttt{RGGGR}，第三次涂成 RGBGR\texttt{RGBGR}，达到目标。

用尽量少的涂色次数达到目标。

长度 n≤50n\le 50。

考虑区间 dp。设 dpi,jdp_{i,j} 表示区间 [i,j][i,j] 的最少涂色次数。

怎么转移？

先考虑如下引理：
存在一种最优操作，每次操作的区间为 [l1,r1],[l2,r2],…,[lm,rm][l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]，这些区间不相交。（要么包含，要么相离）
证明：若存在两个相交区间 [li,ri],[lj,rj] (i<j)[l_i,r_i],[l_j,r_j]\ (i<j)，则可以发现 [li,ri][l_i,r_i] 覆盖的一部分被 [lj,rj][l_j,r_j] 重新覆盖了，那么一开始就不相交，对答案也没有影响，因此不相交。

边界条件为 dpi,i=1dp_{i,i}=1，我们考虑其余的转移。
对于 dpi,jdp_{i,j} 来说，假设操作区间为 [l1,r1],[l2,r2],…,[lm,rm][l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]。

  1. 操作区间中不存在 [i,j][i,j]
    那么显然区间可以被分成两段 [i,k],[k+1,j][i,k],[k+1,j] 来单独计算答案然后加起来。（因为区间是不相交的）
    即 dpi,j=min⁡i≤k<j(dpi,k+dpk+1,j)dp_{i,j} = \min_{i\le k < j}(dp_{i,k}+dp_{k+1,j})
  2. 操作区间中存在 [i,j][i,j]
    此时区间就不能被分成两段了。
    我们考虑何时需要进行操作 [i,j][i,j]。
    当 si≠sjs_i\neq s_j 时，操作 [i,j][i,j] 显然是无意义的，可以被 [i,j−1][i,j-1] 或 [i+1,j][i+1,j] 替代。
    当 si=sjs_i = s_j 时，操作 [i,j][i,j] 可以帮助我们一次完成 ii 和 jj，此时 dpi,j=dpi+1,jdp_{i,j}=dp_{i+1,j}。并且，当 si=sjs_i=s_j 时，第一类转移也不需要了。

所以，当 si=sjs_i=s_j 时，只需要计算第二类转移，否则只需要计算第一类转移即可。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;

char s[55];
int dp[55][55];

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

题2：不老的传说

U391420 不老的传说

与第一题的变更：① 每次最多涂长度为 kk 的一段。② 在环上。

1≤k≤n≤2001\le k \le n \le 200。

在环上很好处理，直接把序列变成两倍长，然后 dp 就可以了，我们考虑一下长度的限制。

长度的限制体现在：
当 si=sjs_i=s_j 时，我们应该要在 j−i+1≤kj-i+1 \le k 时才能采用第二类转移，否则都要采用第一类转移。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;

int a[405];
int dp[405][405];

int main(){
    memset(dp,0x3f,sizeof(dp));
        
    int n,c,K;
    scanf("%d%d%d",&n,&c,&K);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i+n]=a[i];
    }
    
    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=n*2;i++){
            int j=i+len-1;
            if(i==j)dp[i][j]=1;
            
            else{
                // 只需要在这里刻画长度的限制即可
                if(len<=K && a[i]==a[j])dp[i][j]=dp[i][j-1];
                else for(int k=i;k<j;k++)
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
    }
    
    int ans = 1e9;
    for(int i=1;i<=n;i++)ans = min(ans,dp[i][i+n-1]);
    
    printf("%d\n",ans);
    return 0;
}

题3：String painter

UVA1437 String painter

有两个用小写英文字母组成的等长字符串。你有一个强大的字符串刷子，在这把刷子的帮助下，你可以将一个字符串的一个字串中的字符全部刷成任何你想要的字符。也就是说，用刷子刷过的字串就变成用同一个字母组成的了。现在你想要用这一把刷子把字符串 A 刷成 B，而且要求刷的次数最少。

长度 ≤100\le 100。

先考虑空串到 B 串的操作（即题1），记为 dpdp 数组。
考虑再进行一次 dp，记为 ansians_i，表示把 A 的 [1,i][1,i] 刷成 B 的最小次数。

可以写出方程：
初始条件：ansi=dp1,ians_i = dp_{1,i}
转移：ansi=ansi−1 (ai=bi)ans_i = ans_{i-1}\ (a_i=b_i)
ansi=min⁡1≤j<i(ansj+dpj+1,i) (ai≠bi)ans_i = \min_{1\le j<i}(ans_{j}+dp_{j+1,i})\ (a_i\neq b_i)

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;

char a[105],b[105];
int dp[105][105];
int ans[105];

int main(){
    while(scanf("%s%s",a+1,b+1)==2){
        int n = strlen(a+1);
        memset(dp,0x3f,sizeof(dp));
        for(int len=1;len<=n;len++){
            for(int i=1;i+len-1<=n;i++){
                int j=i+len-1;
                if(i==j)dp[i][j]=1;
                else{
                    if(b[i]==b[j])dp[i][j]=dp[i+1][j];
                    else for(int k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        }
        for(int i=1;i<=n;i++){
            ans[i]=dp[1][i];
            if(a[i]==b[i])ans[i]=ans[i-1];
            else for(int j=1;j<i;j++)ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
        }

        printf("%d\n",ans[n]);
    }
    return 0;
}