变种一

就是01串,方法在下面,懒得解释了,自己看注释吧
题目:问最少能把01串划成几个0101…类型的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
//关键点,类似最长不下降子序列的题目,但是由于是01串,只要管有几个0结尾和1结尾的串就好了
ll c0=0,c1=0;
for(int i=0;i<t.length();i++){
   if(t[i]=='1'){
     if(c0) c0--;//接到0结尾的后面
     c1++;//多了一个以1结尾的串
   }
   else{
     if(c1) c1--;//接到1结尾的后面
     c0++;//多了一个以0结尾的串
   }
 }
 return c0+c1;

变种二

是有有限个结尾的dp

例如牛客周赛题目:把字符串变成相邻字母的ASCALL码之差都一样,求最小操作次数

因为只有26个字母,所以可以直接滚动数组+dp,然后设dp[i][j]表示以第i位结尾改成char('a'+j)的最少修改次数,或者也可以设成改为char('a'+j)后最长的连续长度

最后结论就是模拟26种d(实则只用13种),然后公式中每次只要上面的两个状态就行

1
2
3
4
dp[i][j]=max(dp[i-1][(j-d+26)%26],dp[i-1][(j+d+26)%26])+(s[i]==char('a'+j)?0:1);
//设修改次数
dp[i][j]=max(dp[i-1][(j-d+26)%26],dp[i-1][(j+d+26)%26])+(s[i]==char('a'+j)?1:0);
//设合法长度

又例如div3C:C. Dice Roll Sequence

这题是把一串1-6的数字串改成任意相邻两个数字都和不为7

方法也是如上,要么设修改次数要么设合法长度,我写的还是修改次数

1
2
3
4
5
6
7
8
for(int now=1;now<=6;now++){
  for(int last=1;last<=6;last++){
    if(now!=last&&now+last!=7){
      if(now==a[i]) now_dp[now]=min(now_dp[now],dp[last]);
      else now_dp[now]=min(now_dp[now],dp[last]+1);
    }
  }
}