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