CF1366G-Construct the String

题目:

题目描述:

Let’s denote the function $ f(s) $ that takes a string $ s $ consisting of lowercase Latin letters and dots, and returns a string consisting of lowercase Latin letters as follows:

1. let $ r $ be an empty string;
2. process the characters of $ s $ from left to right. For each character $ c $ , do the following: if $ c $ is a lowercase Latin letter, append $ c $ at the end of the string $ r $ ; otherwise, delete the last character from $ r $ (if $ r $ is empty before deleting the last character — the function crashes);
3. return $ r $ as the result of the function.

You are given two strings $ s $ and $ t $ . You have to delete the minimum possible number of characters from $ s $ so that $ f(s) = t $ (and the function does not crash). Note that you aren’t allowed to insert new characters into $ s $ or reorder the existing ones.

输入格式:

The input consists of two lines: the first one contains $ s $ — a string consisting of lowercase Latin letters and dots, the second one contains $ t $ — a string consisting of lowercase Latin letters ( $ 1 \le |t| \le |s| \le 10000 $ ).

Additional constraint on the input: it is possible to remove some number of characters from $ s $ so that $ f(s) = t $ .

输出格式:

Print one integer — the minimum possible number of characters you have to delete from $ s $ so $ f(s) $ does not crash and returns $ t $ as the result of the function.

样例:

样例输入 1:

1
2

a.ba.b.
abb

样例输出 1:

1

2

样例输入 2:

1
2

.bbac..a.c.cd
bacd

样例输出 2:

1

3

样例输入 3:

1
2

c..code..c...o.d.de
code

样例输出 3:

1

3

思路:

首先有一个很显然的思路，$dp_{i,j}$ 表示 $s_{1\cdots i}$ 匹配$t_{1\cdots j}$要删掉的字符的最小值。 $$dp_{i,j}=min\begin{cases}dp_{i-1,j}+1\dp_{i-1,j-1}& & s_i=t_j\dp_{i-1,j}& & si=’.’&\end{cases}$$

然后我们发现它是假的，因为有可能存在先有一段字符，之后又会出现一段删除 所以我们可以统计一个 nxt 表示上一个清空的位置即可 现在式子变成 $$dp_{i,j}=min\begin{cases}dp_{nxt_i,j}+1\dp_{i-1,j-1}& & s_i=t_j\dp_{i-1,j}& & si=’.’&\end{cases}$$

注意程序中的 nxt 表示下一个清空的位置。

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include "ybwhead/ios.h"
using namespace std;
string s, t;
const int maxn = 1e4 + 10;
int dp[maxn][maxn];
int nxt[maxn];

int main()
{
    yin >> s >> t;
    for (int i = 0; i < s.size(); i++)
    {
        nxt[i] = -1;
        int bal = 0;
        if (s[i] != '.')
            for (int j = i; j < s.size();j++)
            {
                if (s[j] == '.')
                    --bal;
                else
                    ++bal;
                if (!bal)
                {
                    nxt[i] = j;
                    break;
                }
            }
    }
    memset(dp, 0x7f7f7f7f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j <= t.size(); j++)
        {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
            if (j < t.size() && s[i] == t[j])
                dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
            if (s[i] != '.' && nxt[i] != -1)
                dp[nxt[i] + 1][j] = min(dp[nxt[i] + 1][j], dp[i][j]);
        }
    }
    yout << dp[s.size()][t.size()] << endl;
    return 0;
}