[atARC109F]1D Kingdom Builder

标签:bit   第一个   color   class   include   子序列   std   define   size   

考虑最终有石子的位置的状态,判断一种状态是否可行

反过来,依次删除石子,删除条件是:当删除的石子是该段最后一个(即其两边都没有石子了),要求除其以外,每个连续段旁边的两个点都与其颜色不同

构造一种删除方案:

除了最先删除的段以外,必然有一时刻(即该段最后一个位置删除时)其余段旁边的两个点颜色都相同,假设都是颜色$c$,另外一种颜色为$c‘$

接下来,如果一个段内含有$c‘$,那么必然可以直接删除该段且不劣,因此我们删除了所有含有$c‘$的段

而对于剩下的段,其所有位置以及旁边都为颜色$c$,那么若有超过1段,则一定不合法,因此我们要让段尽量长(以包含$c‘$来删除),即在构造段旁边颜色为$c$时,找到第一个$c$即可

总结一下,考虑合法当且仅当存在颜色$c$,满足以下条件:

1.对于最先删除的段,其中包含颜色$c‘$

2.对于最晚删除的段,其与其旁边的位置包含至少两个$c$(即含有$cc$的子序列)

3.对于其余的段,其与其旁边的位置包含一个$cc‘c$的子序列

(特别的,如果仅有1个段必然是可行的)

先枚举颜色$c$,对每一个颜色$c$求出最短的方案再取min即可

考虑dp,用$f_{i,j,0/1,0/1}$表示前$i$个字母,$i$所处的串状态为$j$,是否已经出现要强制最先删除/最后删除的段(不包括$i$所处的段)的最短长度,向后转移即可

状态$j$的定义方式有很多,只需要能够转移、能够确定该串的类型即可(例如与$cc‘c$的最长公共子序列长度/未被选择)

技术图片

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define get_min(x,y) x=min(x,y)
 5 int n,ans,f[N][5][2][2];
 6 char s[N],t[N];
 7 int calc(){
 8     memset(f,0x3f,sizeof(f));
 9     f[0][0][0][0]=0;
10     for(int i=0;i<=n;i++)
11         for(int j=0;j<5;j++)
12             for(int p=0;p<2;p++)
13                 for(int q=0;q<2;q++){
14                     if (t[i+1]==_){//不选 
15                         if (!j)get_min(f[i+1][0][p][q],f[i][j][p][q]);
16                         if (((j==2)||(j==3))&&(!p)&&(s[i+1]==w))get_min(f[i+1][0][1][q],f[i][j][p][q]);
17                         if ((j==3)&&(s[i+1]==w)||(j==4))get_min(f[i+1][0][p][q],f[i][j][p][q]);
18                     }
19                     int jj=max(j,1);
20                     if ((jj==1)&&(s[i]==w))jj=2;
21                     if ((jj==2)&&(s[i+1]==b))jj=3;
22                     if ((jj==3)&&(s[i+1]==w))jj=4;
23                     get_min(f[i+1][jj][p][q],f[i][j][p][q]+1);
24                     if (!p){
25                         int jj=max(j,1);
26                         if ((jj==1)&&(s[i]==w))jj=2;
27                         if ((jj==2)&&(s[i+1]==b))jj=3;
28                         if ((j>=2)&&((jj==2)||(jj==3))&&(s[i+1]==w))jj=4;
29                         get_min(f[i+1][jj][1][q],f[i][j][p][q]+1);
30                     }
31                     if (!q){
32                         int jj=max(j,1);
33                         if ((jj==1)&&(s[i]==w))jj=2;
34                         if ((jj<=3)&&(s[i+1]==b))jj=4;
35                         if ((jj==3)&&(s[i+1]==w))jj=4;
36                         get_min(f[i+1][jj][p][1],f[i][j][p][q]+1);
37                     }
38                 }
39     for(int i=0;i<2;i++)
40         for(int j=0;j<2;j++)ans=min(ans,min(f[n+1][0][i][j],f[n+1][4][i][j]));
41 }
42 int main(){
43     scanf("%d%s%s",&n,s+1,t+1);
44     int x=0,y=0;
45     for(int i=1;i<=n;i++)
46         if (t[i]==o){
47             if (!x)x=i;
48             y=i;
49         }
50     t[n+1]=_;
51     ans=y-x+1;
52     s[0]=w;
53     s[n+1]=b;
54     calc();
55     for(int i=0;i<=n+1;i++)
56         if (s[i]==w)s[i]=b;
57         else s[i]=w;
58     calc();
59     printf("%d",ans);
60 }

View Code

 

[atARC109F]1D Kingdom Builder

标签:bit   第一个   color   class   include   子序列   std   define   size   

原文地址:https://www.cnblogs.com/PYWBKTDA/p/14124420.html

版权声明:完美者 发表于 2020-12-17 12:47:16。
转载请注明:[atARC109F]1D Kingdom Builder | 完美导航

暂无评论

暂无评论...