Educational Codeforces Round 82

發表於 2020-02-13 更新於 2024-10-23 分類於 Codeforces ， Edu Disqus：文章字數： 150 所需閱讀時間 ≈ 1 分鐘

E(DP)

E

T组测试

t和s是字符串

s中能否找两个不共用下标的子序列(不要求连续)，t=concat(s1,s2)

T<=100

|s|,|t| <= 400

枚举t的分割位置

dfs(s中当前匹配位置i,t前段匹配位置j,t后半匹配位置k)

很明显超时。

注意到上面dfs仅返回true/false

也就是dfs(i,j,k)=1/0这种

可以改为（也有贪心关系）,dp[i][j]=最多匹配的k

dfs(i,j,k)=1/0可以考虑 dp[i][j]=max/min(k)