【DP】Bovine Genetics G（P7152）

2024-01-29 23:32

文章标签 dp bovine genetics p7152

本文主要是介绍【DP】Bovine Genetics G（P7152），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

P7152

题目大意

对于一个原串（只有四种字符），先将所有相邻且相同的字符分割开，对分割得到的若干段翻转，得到编辑后的字符串，现在给出编辑后的字符串（有一些位置不确定），问你有多少种符合的原串

解题思路

对于一个编辑后的字符串，考虑对其进行分割，那么分割合法要满足以下两个条件：

每一段中相邻位置不相同（如果相同，那么对于原串肯定会再分割）
对于相邻两段a,b，a的首字符要和b的结尾字符相同（保证在原串中可以被分割）

可以考虑DP，设 $f_{i,ch}$ 为前i个字符已经分割好，且最后一段的首字符为ch的方案数，那么可以从i往后枚举，然后传递

但这样显然会TLE，题目有说到字符串只有四种字符，那么可以考虑从字符下手

设 $f_{i,a,b,c}$ 为前i个字符串已经分割好了，且上一段首字符为a，当前段首字符为b，结尾字符为c的方案数（计算答案的时候保证a,c相同即可）

那么对于新插入的一个字符考虑两种方案：

加入最后一段里，那么要保证新字符和c不同
新开一段，那么要保证a,c不同

这样转移时间复杂度为O(n)，常数为 $4^4$ ，可以过

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100010
#define wyc 1000000007
using namespace std;
int n,ans,v[N],f[N][5][5][5];
char c[N];
int main()
{scanf("%s",c+1);n=strlen(c+1);for(int i=1;i<=n;++i){if(c[i]=='?')v[i]=0;else if(c[i]=='A')v[i]=1;else if(c[i]=='C')v[i]=2;else if(c[i]=='G')v[i]=3;else v[i]=4;}for(int i=1;i<=4;++i)for(int j=1;j<=4;++j)if(v[1]==j||!v[1])f[1][i][j][j]=1;for(int i=1;i<n;++i)for(int c=1;c<=4;++c)if(!v[i]||v[i]==c)for(int a=1;a<=4;++a)for(int b=1;b<=4;++b){if(!v[i+1]){for(int d=1;d<=4;++d){//？的情况if(a==c)(f[i+1][b][d][d]+=f[i][a][b][c])%=wyc;if(c!=d)(f[i+1][a][b][d]+=f[i][a][b][c])%=wyc;}}else{if(a==c)(f[i+1][b][v[i+1]][v[i+1]]+=f[i][a][b][c])%=wyc;if(c!=v[i+1])(f[i+1][a][b][v[i+1]]+=f[i][a][b][c])%=wyc;}}for(int a=1;a<=4;++a)for(int b=1;b<=4;++b)(ans+=f[n][a][b][a])%=wyc;printf("%d",ans);return 0;
}