hdu6485
链接
题意
给两个串s,t长度都小于4000,再给一个k<4000,求s和t各自的最长子串,使这两个子串间最多k个不同的字符,题解
dp[i][j]代表串s以i结束,t以j结束,最多k个字符不同的最小起点在哪,显然dp[i+x][j+x]的值关于x单调
于是我们就可以O(n^2)完成了
然后优化空间就行了。
- 本文作者: fightinggg
- 本文链接: http://fightinggg.github.io/yilia/yilia/hdu6485.html
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!