题目
题目链接:https://www.luogu.com.cn/problem/U142584
Peter 给 Jack 展示了 (n) 个长度相同的 (01) 串,记两个 (01) 串 (x,y) 的拼接操作为 (f(x,y))。则 (f(x,y)=) 以 (x) 为前缀, 以 (y) 为后缀的最短的串。
并定义 (f(x)=x,f(a_1,a_2...a_k)=f(f(a_1,a_2...a_{k-1}),a_k)) 现在 Peter 要求 Jack 将给出的 (n) 个 (01) 串序列 (a_1,a_2...a_n) 分成两个没有交集的子序列 (b_1,b_2...b_k) 和 (c_1,c_2...c_m),且 (m+k=n)。要求 (f(b_1,b_2...b_k)) 与 (f(c_1,c_2...c_m)) 的长度之和最小。求这个最小的长度之和。
思路
显然在拼接好第 (i) 个串之前,两个串中一定有一个末尾的串是 (i-1)。
设 (f[i][j][k]) 表示拼接完前 (i) 个串,两个序列中最后一个串非 (i) 的那一个的最后 (j) 位的状态为 (i-1) 的最小长度。
设 (calc(i,j)) 表示将 (i) 串和 (j) 串拼起来后需要增加的长度。考虑拼第 (i) 个串的过程:
- 如果将第 (i) 个串拼到第 (i-1) 个串上,那么 (f[i][j][k]=f[i-1][j][k]+calc(i-1,i))。
- 如果将第 (i) 个串拼到另一个串上,那么 (f[i][j][mathrm{suf}(i-1,j)]=min(f[i-1][l][mathrm{pre}(i,l)]))。
直接转移是 (O(nm2^m)) 的。主要复杂度花费与第一个转移。发现第一个转移均为 (i-1) 转移到 (i),(j,k) 不变,但是权值要加上 (calc(i-1,i)),所以我们可以将每一次转移都直接减去 (calc(i-1,i)),然后最后输出时加上减去的部分。
这样方程就变为了
发现第二个方程是直接取 (min),可以将第一位扔掉。那么将 (i) 这一维去掉之后第一个方程就没有用了。
时间复杂度 (O(nm))。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=200010,M=25,MAXN=(1<<20);
int n,m,ans,pre[N][M],suf[N][M],f[M][MAXN];
char s[M];
int calc(int i,int j)
{
for (int k=m;k>=1;k--)
if (suf[i][m-k+1]==pre[j][k]) return m-k;
return m;
}
int main()
{
scanf("%d%s",&n,s+1);
m=strlen(s+1);
for (int i=1;i<=n;i++)
{
if (i>1) scanf("%s",s+1);
for (int j=1;j<=m;j++)
pre[i][j]=(pre[i][j-1]<<1)+s[j]-48;
for (int j=m;j>=1;j--)
suf[i][j]=suf[i][j+1]+((s[j]-48)<<(m-j));
}
memset(f,0x3f3f3f3f,sizeof(f));
memset(suf[0],-1,sizeof(suf[0]));
f[0][0]=0;
for (int i=1;i<=n;i++)
{
int minn=2e9,res=calc(i-1,i);
for (int j=0;j<=m;j++) minn=min(minn,f[j][pre[i][j]]+m-j-res);
for (int j=0;j<=m;j++) f[j][suf[i-1][m-j+1]]=min(f[j][suf[i-1][m-j+1]],minn);
ans+=res;
}
printf("%d",f[0][0]+ans);
return 0;
}