hdu6485

转移自老blog

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)完成了
        然后优化空间就行了。

hdu6485
http://fightinggg.github.io/fluid/hdu6485.html
作者
fightinggg
发布于
2019年8月5日
许可协议