spoj 1812 LCS2（SAM+DP）
【题目链接】http://www.spoj.com/problems/LCS2/en/【题意】求若干个串的最长公共子串。【思路】SAM+DP先拿个串建个SAM，然后用后面的串匹配，每次将所有的匹配长度记录在状态上取min，然后对所有状态取max即答案。需要更新fa，因为fa[p]一定比p更优，但匹配...
uva 111 - History Grading (dp, LCS)
题目链接题意：给N，第二行是答案，n个数c1---cn, 代表第一个的顺序是c1，第二个数顺序是c2;下面每一行是学生的答案，格式同上。注意：这个给的顺序需要处理一下，不能直接用。思路：LCS。 #include <iostream> #include <cstdio> #i...
UVA 11404 Palindromic Subsequence[DP LCS 打印]
UVA-11404PalindromicSubsequence题意：一个字符串，删去0个或多个字符，输出字典序最小且最长的回文字符串不要求路径区间DP都可以做然而要字典序最小倒过来求LCS，转移同时维护f[i][j].s为当前状态字典序最小最优解f[n][n].s的前半部分一定是回文串的前半部分(想...
洛谷P4590 [TJOI2018]游园会(状压dp LCS)
题意题目链接Sol这个题可能是TJOI2018唯一的非模板题了吧。。考虑LCS的转移方程，\[f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+(A_i=B_j))\]也就是说我们如果知道了前一个列向量\(f[i-1]\)以及\(A_i,B_j\)我们就可以转移...