Albocede DNA
This is a hard DP problem. The key is to find the iteration formular. Let's first consider a simpler problem
in which we only need to guarantee that the subsequence is in a form of aaabbbcccddd
. In other words,
each letter appears more than once and they are in a order of abcd
.
As for the simpler problem. We use DP[i][j] denotes the count of subsequence in string str[0..i]
that
ends in letter j
. So we have:
- if
str[i] == 'a'
, DP[i][0]=DP[i−1][0]×2+1. - if
str[i] == 'b'
, DP[i][1]=DP[i−1][1]×2+DP[i−1][0]. - if
str[i] == 'c'
, DP[i][2]=DP[i−1][2]×2+DP[i−1][1]. - if
str[i] == 'd'
, DP[i][3]=DP[i−1][3]×2+DP[i−1][2].
The result is DP[n][3].
As for our original problem. We have to seperate the cases of DP[i][j] to several cases to enable
controlling of letter count. Let DP[i][j][k][c] means the count of valid subsequence ends with
letter c and the number of a
s minus number of c
s is j and the number of b
s minus the
number of d
s is k. As all a
s is in front of c
s and all b
s is in front of d
s, there is
no point to record the cases that j < 0
and k < 0
as we won't start from those states to produce
a valid subsequence.
After reduced the space uses, we can get a solution like:
import java.io.*;
import java.util.*;
public class AlbocedeDNA {
static private int MOD = 1000000007;
static private int[][][] dp = new int[512][512][4];
private static int solve(String s) {
for (int i = 0; i < 512; i++) {
for (int j = 0; j < 512; j++) {
for (int k = 0; k < 4; k++) {
dp[i][j][k] = 0;
}
}
}
char[] str = s.toCharArray();
int n = str.length;
for (int i = 1; i <= n; i++) {
char c = str[i - 1];
if (c == 'a') {
for (int j = i; j >= 0; j--) {
dp[j + 1][0][0] = (dp[j + 1][0][0] + dp[j][0][0]) % MOD;
}
dp[1][0][0] = (dp[1][0][0] + 1) % MOD;
dp[1][0][0] = (dp[1][0][0] + dp[0][0][3]) % MOD;
} else if (c == 'b') {
for (int j = 0; j < i; j++) {
for (int k = i; k >= 0; k--) {
dp[j][k + 1][1] = (dp[j][k + 1][1] + dp[j][k][1]) % MOD;
}
dp[j][1][1] = (dp[j][1][1] + dp[j][0][0]) % MOD;
}
} else if (c == 'c') {
for (int k = 0; k < i; k++) {
for (int j = 0; j < i; j++) {
dp[j][k][2] = (dp[j][k][2] + dp[j + 1][k][2]) % MOD;
dp[j][k][2] = (dp[j][k][2] + dp[j + 1][k][1]) % MOD;
}
}
} else {
for (int j = 0; j < i; j++) {
for (int k = 0; k < i; k++) {
dp[j][k][3] = (dp[j][k][3] + dp[j][k + 1][3]) % MOD;
dp[j][k][3] = (dp[j][k][3] + dp[j][k + 1][2]) % MOD;
}
}
}
}
return dp[0][0][3];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for (int t = 0; t < N; t++) {
System.out.printf("Case #%d: %d\n", t + 1, solve(in.next()));
}
}
}