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\)我们就可以转移...