题解：P7152 [USACO20DEC] Bovine Genetics G

Solution

一个比较显然的是，开始时的基因组序列的数量，就等于每种编辑后的基因组序列所有合法的划分方案数总和。

证明很简单，就是因为对于每一个开始时的基因组序列，有且仅有一种满足题意的划分方案。

那么考虑对于一个编辑后的基因组序列，使其一种合法划分方案需要满足什么性质。

首先要满足对于任意一段

\left[L, R\right]

中，不存在

i, j \in \left[L, R\right]

且

i \neq j

，满足

s_i = s_j

。其次，第

i

段的开头等于第

i + 1

段的结尾。

那么考虑 dp，设

f_{i, a, b, c}

表示前

i

个位置，最后一个段的结尾是

a

，开头是

c

，倒数第二段翻转后的开头是

b

。转移是显然的。

时间复杂度

O(|\Sigma|^4n)

。

AC Code

CPP

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 1e5 + 5, mod = 1e9 + 7;
long long f[N][4][4][4];
char s[N];
int n, mp[200];
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	mp['A'] = 0, mp['G'] = 1, mp['C'] = 2, mp['T'] = 3;
	cin >> s + 1;
	n = strlen(s + 1);
	For(i, 0, 3) {
		if (s[1] == '?') For(j, 0, 3) f[1][j][i][j] = 1;
		else f[1][mp[s[1]]][i][mp[s[1]]] = 1;
	}
	For(i, 2, n) For(j, 0, 3) {
		if (!(s[i] == '?' || mp[s[i]] == j)) continue;
		For(k, 0, 3) For(a, 0, 3) For(b, 0, 3) {
			if (j != k) f[i][j][a][b] = (f[i][j][a][b] + f[i - 1][k][a][b]) % mod;
			if (a == k) f[i][j][b][j] = (f[i][j][b][j] + f[i - 1][k][a][b]) % mod;
		}
	}
	long long ans = 0;
	For(i, 0, 3) {
		if (!(s[n] == '?' || mp[s[n]] == i)) continue;
		For(j, 0, 3) ans = (ans + f[n][i][i][j]) % mod;
	}
	cout << ans;
	return 0;
}

题解：P7152 [USACO20DEC] Bovine Genetics G

文章操作

Solution

相关推荐

评论

题解：P7152 [USACO20DEC] Bovine Genetics G