我们尝试给这个抽象题来一篇题解。
思考过程还是很重要的。
首先看了这个题,一看数据范围 \(n\le 50\),然后就不懂了,你告诉我这玩意可以状压??
然后我们一顿乱想,发现如果 \(n\) 除以一个 \(3\),那我们是不是就可以状压了。
那怎么除以 \(3\) 呢。
接着我们手玩一下样例,发现似乎这个答案他不是很小啊。
然后我们继续,我们发现,如果答案够大,那么我们公共子序列的两对匹配点,假设在 \(S,T\) 分别为 \((i_1,j_1),(i_2,j_2)\),他就可以保证 \(|\max \{i_2-i_1,j_2-j_1\}|\le n-ans\)。
所以,如果我们的答案 \(ans \ge \dfrac{n}{3}\)(向下取整),那我们就可以把两对匹配点之间的交换状况直接状压出来。
那么我们胡乱证明一下:
我们可以把这个序列分成若干个长度为 \(3\) 的连续段,例如 \([1,3],[4,6],[7,9]\) 之类。
然后由于 \(S_i,T_i\in\{X,Y\}\),所以我们可以在里面把 \(2^6\) 种情况全部暴力枚举出来,然后发现里面至少会产生一个长度为 \(2\) 的公共子序列,所以答案必然 \(\ge \dfrac{2n}{3}\)。
最终我们就通过一系列联想得到了这个结论。
然后有一个非常重要的东西,如果我们把 \(X\) 当作 \(1\),\(Y\) 当作 \(0\),那么最终答案就是这个二进制串的最大值,完美将方案输出,字典序最小,还有个数最大结合在一起。
然后我们考虑怎么状压。
这个状态是真的抽象啊,考场上纯属乱想的状态,好难解释。。
我们定义 \(dp_{i,ST}\),表示当前在 \(S,T\) 中考虑到了 \(i\),从上次匹配点到当前点的状态为 \(ST\) (这个 \(ST\) 我很难解释,就是指在中间这一段中,你的 \(S,T\) 可以取的字符,\(X\) 为 \(1\),\(Y\) 为 \(0\),由于可以交换,所以我们就将 \(S,T\) 不区分开,不然你对两个都要打一个状态),的最小字典序(这个字典序就用上述的二进制串表示,其实就是这个二进制串的最大值)。
考虑顺推,这逆推太难了。
以及,为了方便,我们将 \(1\) 作为初始状态,因为我们后面要从最高位开始向下找第一个满足条件的,所以需要先把最高位立在前面。
我们钦定 \(S_i=X\) 是,\(a_i=0\),否则 \(a_i=1\)。对于 \(T_i\) 对应 \(b_i\) 同理。
然后,如果我们不在这一步进行匹配,由于没有区分 \(S,T\),就有下面两种情况:
-
\(dp_{i+1,ST<<1|a_i} = \max\{dp_{i+1,ST<<1|a_i},dp_{i,ST}\}\)
-
\(dp_{i+1,ST<<1|b_i} = \max\{dp_{i+1,ST<<1|b_i},dp_{i,ST}\}\)
(当然,进行这一步的前提是,你左移之后不会超过 \(2^{\frac{2n}{3}}\))
接着,如果我们要用 \(S_i,T_i\) 进行匹配,那么分为 \(3\) 种情况:
-
用 \(S_i\) 匹配 \(T_i\),也就是 \(S_i=T_i\) 时。那么显然有 \(dp_{i+1,0} = \max \{ dp_{i+1,0},dp_{i,ST} << 1|a_i\}\)。
-
用 \(S_i\) 匹配前面的状态。我们从最高位开始(因为是左移,所以越高位越前面,而我们当然贪心的希望去选前面的符合要求的来匹配)找到第一个二进制位上等于 \(a_i\) 的位置,将后面全部删掉,然后再将 \(b_i\) 加入这个状态的首位(因为他没使用),假设操作完毕的状态为 \(nxt\),那么有 \(dp_{i+1,nxt}=\max \{dp_{i+1,nxt},dp_{i,ST}<<1|a_i\}\)。
-
用 \(T_i\) 同理,将第二种情况的 \(a,b\) 和 \(S,T\) 交换一下就行。
由于此时时间复杂度已经达到 \(n\times 2^{\frac{n}{3}}\),所以对于 \(nxt\),我们直接用一个 \(Nxt[ST][0/1][0/1]\) 来预处理即可。
这部分之前考试都有想到,但是范智打错。。
我们可以在思考一下正确性,就是你每次遇到 \(S_i,T_i\) 要么将两者互相匹配,要么在后续状态中也只会选择其中的一个进行匹配,故状态只需要维护一个。
最后找到 \(dp_{n,i}\) 的最大值(因为是二进制串),然后转化为 \(X,Y\) 输出即可。
话说这题二进制串的到处乱移是真恶心。
\(\texttt{Code}\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long dp[65][1 << 21];
int nxt[1 << 21][2][2];
int n;
char a[65], b[65];
signed main()
{
// freopen("try.in", "r", stdin);
// freopen("try.out", "w", stdout);
scanf("%lld", &n);
scanf("%s", a + 1), scanf("%s", b + 1);
int limit = ceil(n / 3.0);
for (int i = 1; i < (1 << limit); ++i)
{
for (int j = 0; j < 2; ++j)
{
for (int k = 0; k < 2; ++k)
{
int pos = -1;
for (int l = (__lg(i) - 1); l >= 0; --l) if(((i >> l) & 1) == j)
{
pos = l;
break;
}
if(pos == -1) continue;
nxt[i][j][k] = (((i & ((1ll << pos) - 1)) + (1 << pos)) << 1) + k;
}
}
}
dp[0][1] = 1;
for (int i = 0; i < n; ++i)
for (int j = 0; j < (1 << limit); ++j)
{
if(!dp[i][j]) continue;
int p = (a[i + 1] == 'X'), q = (b[i + 1] == 'X');
if(nxt[j][p][q]) dp[i + 1][nxt[j][p][q]] = max(dp[i + 1][nxt[j][p][q]], (dp[i][j] << 1) + p);
if(nxt[j][q][p]) dp[i + 1][nxt[j][q][p]] = max(dp[i + 1][nxt[j][q][p]], (dp[i][j] << 1) + q);
if(((j << 1) + p) < (1 << limit)) dp[i + 1][(j << 1) + p] = max(dp[i + 1][(j << 1) + p], dp[i][j]);
if(((j << 1) + q) < (1 << limit)) dp[i + 1][(j << 1) + q] = max(dp[i + 1][(j << 1) + q], dp[i][j]);
if(p == q) dp[i + 1][1] = max((dp[i][j] << 1) + p, dp[i + 1][1]);
}
long long ans = 0;
for (int i = 0; i < (1 << limit); ++i) ans = max(ans, dp[n][i]);
int cnt = __lg(ans);
for (int i = cnt - 1; i >= 0; --i) if((ans >> i) & 1) putchar('X'); else putchar('Y');
return 0;
}
标签:nxt,匹配,状态,题解,Ladder,ST,XY,我们,dp
From: https://www.cnblogs.com/SFsaltyfish/p/18059182