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;
}