p*****2
发帖数: 21240 | 1 一个String有sub string 和 sub sequence.
sub string大家都知道，sub sequence就是可以不连续的sub string。
比如abc, ab, bc 都是substring, 而ac不是。但是，ac也是sub sequence。
现在给两个String， s和t
那么在s里选取一个substring， 在t里选取一个sub sequence，使得他们相等。
问可以选取多少种组合。sub string , sub sequence 内容相等不要紧，只要有字符的
位置不同就认为是不同的string。
比如
s: "aa"
t: "aa"
ans: 5 |
s******n
发帖数: 3946 | |
g*********e
发帖数: 14401 | |
p*****2
发帖数: 21240 | 4
暴力不行。这是到DP题。代码量很少。
【在 g*********e 的大作中提到】
: 暴力数？
|
l******e
发帖数: 149 | |
a***g
发帖数: 234 | 6 n^2吧
【在 l******e 的大作中提到】
: 用DP, 复杂度n3
|
p*****2
发帖数: 21240 | 7
大牛给讲一讲。
【在 a***g 的大作中提到】
: n^2吧
|
z********c
发帖数: 72 | 8 我的想法
F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
方案数
1. S[i]!=T[j]，则F[i][j]=0
2. S[i]==T[j]，则
a. i和j分别都是各自的第一个字符，方案数1
b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
so
F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
设
S[i][j] = F[i][1] + F[i][2] + ... F[i][j]
所以
F[i][j] = 1 + S[i - 1][j - 1]
S[i][j] = S[i][j - 1] + F[i][j]
answer = sigma (F[i][j]), i <= len (s), j <= len(t)
【在 a***g 的大作中提到】
: n^2吧
|
p*****2
发帖数: 21240 | 9
你这么牛还需要多准备一个星期面F吗？
【在 z********c 的大作中提到】
: 我的想法
: F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
: 方案数
: 1. S[i]!=T[j]，则F[i][j]=0
: 2. S[i]==T[j]，则
: a. i和j分别都是各自的第一个字符，方案数1
: b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
: so
: F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
: 设
|
z********c
发帖数: 72 | 10 您搞笑了，刚才的G电面就跟坨屎一样。。。
【在 p*****2 的大作中提到】
:
: 你这么牛还需要多准备一个星期面F吗？
|
|
|
h**6
发帖数: 4160 | |
i**********e
发帖数: 1145 | 12 应该不会吧，以你的实力来看的话。
【在 h**6 的大作中提到】
: 楼主你的F面完了吗，我刚去了估计没戏。
|
a***g
发帖数: 234 | 13 M[i, j]: 以s[i]为结束的substring匹配t[0-j]的方案数
case 1: s[i] == t[j]
M[i, j] = M[i-1, j-1] + M[i, j-1] + 1
case 2: s[i] != t[j]
M[i, j] = M[i, j-1]
最后结果为: M[0, n-1] + M[1, n-1] + ... + M[n-1, n-1]
对么？
【在 a***g 的大作中提到】
: n^2吧
|
p*****2
发帖数: 21240 | 14
这题对我来说太复杂了。看了你的解释才有点头绪。晚上在好好看看。
【在 z********c 的大作中提到】
: 我的想法
: F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
: 方案数
: 1. S[i]!=T[j]，则F[i][j]=0
: 2. S[i]==T[j]，则
: a. i和j分别都是各自的第一个字符，方案数1
: b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
: so
: F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
: 设
|
b***e
发帖数: 1419 | 15 This seems to be O(n^3). I believe there's O(n^2).
【在 z********c 的大作中提到】
: 我的想法
: F[i][j]为S的substring最后取得位置是i，T的sub sequence最后取得位置是j，匹配的
: 方案数
: 1. S[i]!=T[j]，则F[i][j]=0
: 2. S[i]==T[j]，则
: a. i和j分别都是各自的第一个字符，方案数1
: b. i和j不是第一个字符，那么方案数F[i - 1][k] k < j
: so
: F[i][j] = 1 + sum (F[i - 1][1] + F[i - 1][2] .. F[i][j - 1])
: 设
|
S******t
发帖数: 151 | 16 Arxor?
【在 z********c 的大作中提到】
: 您搞笑了，刚才的G电面就跟坨屎一样。。。
|
p*****2
发帖数: 21240 | 17 费了老半天劲写了一个恶心的。
int[][] dp = new int[2][];
void run()
{
Scanner in = new Scanner(System.in);
out = new PrintWriter(System.out);
char[] s = in.next().toCharArray();
char[] t = in.next().toCharArray();
int slen = s.length;
int tlen = t.length;
int mod = 1000000007;
dp[0] = new int[tlen];
dp[1] = new int[tlen];
int total = 0;
for (int j = 0; j < tlen; j++)
{
if (s[0] == t[j])
{
total++;
dp[0][j] = 1;
}
}
for (int i = 1; i < slen; i++)
{
if (s[i] == t[0])
{
dp[1][0] = 1;
total++;
}
int sum = 0;
for (int j = 1; j < tlen; j++)
{
sum += dp[0][j - 1];
sum %= mod;
if (s[i] == t[j])
{
dp[1][j] = sum + 1;
total += sum + 1;
total %= mod;
}
}
int[] tmp = dp[0];
dp[0] = dp[1];
dp[1] = tmp;
Arrays.fill(dp[1], 0);
}
out.println(total);
out.close();
} |
l***i
发帖数: 1309 | 18 The original problem is from codeforces.com, VK cup round 2, problem A. The
constraints ask for O(n^2) solution as n=5000. |
