洛谷P4590 [TJOI2018]游园会(状压dp LCS)
程序员文章站
2022-06-11 08:31:44
题意 "题目链接" 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 ......
题意
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\)我们就可以转移了
那么可以暴力dp,\(f[i][sta][0/1/2]\)表示到第\(i\)个位置,当前lcs数组为sta的方案数,但是这个状态显然是\(k^k\)的。观察到一个性质:sta中的每个位置最多与前一个位置相差为\(1\),那么其实只需要记录一个差分数组就可以了。转移到的状态可以预处理。
复杂度\(o(9 * n * 2^k)\)
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10, mod = 1e9 + 7; template <typename a, typename b> inline int add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;} template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);} inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, k; int f[2][(1 << 15) + 1][3], trans[(1 << 15) + 1][3], one[(1 << 15) + 1], ans[16]; char s[maxn], ss[5] = "noi"; int get(int sta, int c) { int pre[16] = {}, nw[16] = {}; for(int i = 1; i <= k; i++) pre[i] = pre[i - 1] + ((sta >> (i - 1)) & 1); for(int i = 1; i <= k; i++) { if(ss[c] == s[i]) nw[i] = pre[i - 1] + 1; else nw[i] = max(nw[i - 1], pre[i]); } int ans = 0; for(int i = 1; i <= k; i++) ans += (nw[i] - nw[i - 1]) << (i - 1); return ans; } signed main() { n = read(); k = read(); scanf("%s", s + 1); f[0][0][0] = 1; int lim = 1 << k; for(int sta = 0; sta < lim; sta++) { one[sta] = one[sta >> 1] + (sta & 1); for(int i = 0; i < 3; i++) trans[sta][i] = get(sta, i); } int o = 0; for(int i = 0; i <= n; i++) { memset(f[o ^ 1], 0, sizeof(f[o ^ 1])); for(int sta = 0; sta < lim; sta++) { for(int len = 0; len < 3; len++) { for(int c = 0; c < 3; c++) { int nxt; if(c == 0) nxt = 1; else if(c == 1) nxt = (len == 1 ? 2 : 0); else if(c == 2) nxt = (len == 2 ? 3 : 0); if(nxt == 3) continue; add2(f[o ^ 1][trans[sta][c]][nxt], f[o][sta][len]); } // cout << f[i + 1][sta][len] << '\n'; } } o ^= 1; } for(int i = 0; i < lim; i++) for(int j = 0; j < 3; j++) add2(ans[one[i]], f[o ^ 1][i][j]); for(int i = 0; i <= k; i++) cout << ans[i] << '\n'; return 0; } /* */
上一篇: 压缩测试