nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

hdu6485

链接

http://acm.hdu.edu.cn/showproblem.php?pid=6485

题意

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