Atcoder 452 D
原文链接：https://www.cnblogs.com/Time25/p/19836648.html
题目
https://atcoder.jp/contests/abc452/tasks/abc452_d
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string s,t;cin>>s>>t;
vector<int>dp(t.length(),-1);
vector<vector<int>>idx(26);
for(int i=t.length()-1;i>=0;i--){
idx[t[i]-'a'].push_back(i);
}
//这里为什么是倒序存储的t的？
int ans=0;
for(int i=0;i<s.length();i++){
for(int j:idx[s[i]-'a']){
if(j==0)dp[0]=i;
else dp[j]=dp[j-1];
}
ans+=i-dp[t.length()-1];
}
cout<<ans<<endl;
}为什么是反序的呢？
得明确的就是：dp[j]是指可以凑齐j+1个字母最晚可以从哪个地方开始
为什么是反序：
例子：
2
3
4
5
6
7
8
9
10
11
12
13
t = "aa"
dp = [-1, -1]
i=0, s[0]='a':
遍历 idx['a'] = {0, 1} // 正序
j=0: dp[0] = 0
j=1: dp[1] = dp[0] = 0 // ✓ 正确
i=3, s[3]='a':
遍历 idx['a'] = {0, 1} // 正序
j=0: dp[0] = 3 // ❌ 问题！覆盖了之前的值
j=1: dp[1] = dp[0] = 3 // ❌ 错误！应该是0
2
3
4
5
6
7
8
9
10
11
12
dp = [-1, -1]
i=0, s[0]='a':
遍历 idx['a'] = {1, 0} // 倒序
j=1: dp[1] = dp[0] = -1 // dp[0] 还是 -1，不对...
j=0: dp[0] = 0
i=3, s[3]='a':
遍历 idx['a'] = {1, 0} // 倒序
j=1: dp[1] = dp[0] = 0 // ✓ 正确！保持之前的值
j=0: dp[0] = 3 // 更新 dp[0]
