BYR Achieve · 镜像论坛

The DNA of the Albocede alien species is made up of 4 types of nucleotides: a, b, c, and d. Different Albocedes may have different sequences of these nucleotides, but any Albocede's DNA sequence obeys all of the following rules: 1.It contains at least one copy of each of a, b, c, and d. 2.All as come before all bs, which come before all cs, which come before all ds. 3.There are exactly as many 'a's as 'c's. 4.There are exactly as many 'b's as 'd's. For example, abcd and aabbbccddd are valid Albocede DNA sequences. acbd, abc, and abbccd are not. The Albocede-n is an evolved species of Albocede. The DNA sequence of an Albocede-n consists of one or more valid Albocede DNA sequences, concatenated together end-to-end. For example, abcd and aaabcccdaabbbccdddabcd are valid Albocede-n DNA sequences. (Observe that a valid Albocede-n DNA sequence is not necessarily also a valid Albocede DNA sequence.) From one of your alien expeditions, you retrieved an interesting sequence of DNA made up of only as, bs, cs, and ds. You are interested in how many of the different subsequences of that sequence would be valid Albocede-n DNA sequences. (Even if multiple different selections of nucleotides from the sequence produce the same valid subsequence, they still all count as distinct subsequences.) Since the result may be very large, please find it modulo 1000000007 (109 + 7). Input The first line of the input gives the number of test cases, T. Each of the next T lines contains a string S that consists only of the characters a, b, c, and d. Output For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the output of the xth test case. 大意就是说有一个abcd构成的A-DNA字符串，一个正确的A-DNA串至少要包含abcd各一次，并且所有a出现在所有b的前面，所有b出现在所有c的前面，所有c出现在所有d的前面，串中a的个数和c相等，b的个数和d相同，然后一个A-N-DNA串是包含N个合格的DNA串首尾相连构成的。现在给一个字符串S，问他的subsequence能构成多少种A-N-DNA串，只要选择了不同位置字符构成的子串就算作不同的A-N-DNA串。肿么考虑呢？另，down了一份别人的答案，思路是dp的，有点不明白，代码如下： #include <cstdio> #include <algorithm> #define N 505 #define M 1000000007 #define fi(a, b, c) for(int a = (b); a < (c); a++) #define fd(a, b, c) for(int a = (b); a > (c); a--) #define FI(a, b, c) for(int a = (b); a <= (c); a++) #define FD(a, b, c) for(int a = (b); a >= (c); a--) #define fe(a, b, c) for(int a = (b); a; a = c[a]) using namespace std; int t, n, dp[N][N][N][2]; char s[N]; void add(int &a, int b){ a += b; if(a > M) a -= M; } void solve(int tc){ scanf("%s", s); for(n = 0; s[n]; n++); FI(i, 0, n) FI(j, 0, n / 2) FI(k, 0, n / 2) fi(l, 0, 2) dp[i][j][k][l] = 0; dp[0][0][0][0] = 1; FI(i, 1, n){ FI(j, 0, n / 2) FI(k, 0, n / 2) fi(l, 0, 2){ if(s[i - 1] == 'a'){ if(!k) add(dp[i][j + 1][k][0], dp[i - 1][j][k][l]); } if(s[i - 1] == 'b'){ if(j && !l) add(dp[i][j][k + 1][0], dp[i - 1][j][k][l]); } if(s[i - 1] == 'c'){ if(j && k) add(dp[i][j - 1][k][1], dp[i - 1][j][k][l]); } if(s[i - 1] == 'd'){ if(!j && k && l) add(dp[i][j][k - 1][1], dp[i - 1][j][k][l]); } add(dp[i][j][k][l], dp[i - 1][j][k][l]); } //FI(j, 0, n / 2) FI(k, 0, n / 2) fi(l, 0, 2) if(dp[i][j][k][l]) // printf("%d %d %d %d %d\n", i, j, k, l, dp[i][j][k][l]); } printf("Case #%d: %d\n", tc, dp[n][0][0][1]); } int main(){ freopen("D-small-attempt0.in", "r", stdin); freopen("D-small-attempt0.out", "w+", stdout); scanf("%d", &t); FI(z, 1, t) solve(z); scanf("\n"); } 感觉大致意思应该是dp[i][j][k][l],到字符串的i位置为止，j表示a和c构成的差值，类似检查左右括号一样，是a就+1，是c就-1，然后k是b和d的，l表示什么一直没想明白。递推规则感觉大致是：对于第i个字符，如果符合A-DNA串规则的话，选择这个字符改变j和k得到下一个状态，或者不选择，直接加上i-1状态的值。然而，还是不明l表明什么，为什么l是2维的，这个递推关系究竟是如何考虑的，求各位大神解惑啊！

请问一个g的笔试题