两个子序列(？标识符)
Problem 1 两个子序列(twosub.pas/c/cpp)
【题目描述】
将给定的n个长度为M的01串序列{a1,a2…an} 分为两个子序列{b1,b2…bk}和{c1,c2…cm}，m+k=n,使|f(b1,b2…bk)|+|f(c1,c2…cm)|最小化。
f函数定义如下：
f(空序列)=空串
f(s)=s
f(s1,s2)=最小长度的有一个前缀等于s1并且有一个后缀等于s2的字符串。 f(a1,a2,…,an)=f(f(a1,a2,…,an-1),an)。
【输入格式】
第一行两个整数n。
接下来n行每行一个长度为M的01串，表示a1，a2...an。
【输出格式】
输出一个整数，表示答案。
【样例输入】
4
000
111
110
001
【样例输出】
8
【数据范围】
对于30%的数据，n<=20
对于60%的数据，n<=2000
对于100%的数据，1<=n<=200000，1<=M<=20
这题要用后缀DP
f[i][j]表示非当前枚举点结尾的那个字符串结尾为i
#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<functional>#include<cmath>#include<iostream>using namespace std;#define MAXN (200000+10)#define MAXM (20+10)#define MAXSum (1<<20)int n,m,f[MAXSum][MAXM],a[MAXN],bin[MAXM];char s[MAXM];int main(){freopen("twosub.in","r",stdin);freopen("twosub.out","w",stdout);scanf("%d",&n);memset(f,128,sizeof(f));memset(a,0,sizeof(a));for (int i=1;i<=n;i++){scanf("%s",s);m=strlen(s);for (int j=0;j<m;j++) a[i]=(a[i]<<1)+s[j]-48;}int tot=0;bin[0]=0;for (int i=1;i<=20;i++) bin[i]=(1<<i)-1;int ans=n*m;for (int i=2;i<=n;i++){int k=m;while (k&&((bin[k]&a[i-1])!=a[i]>>(m-k))){//cout<<(bin[k]&a[i-1])<<' '<<a[i]<<m-k<<(a[i]>>(m-k))<<endl;k--;}//cout<<k<<endl;ans-=k;int temp=0;for (int j=0;j<=m;j++) temp=max(temp,f[a[i]>>j][m-j]+m-j);for (int j=0;j<=m;j++) f[a[i-1]&bin[j]][j]=max(f[a[i-1]&bin[j]][j],temp-k);}int temp=0;for (int j=0;j<=m;j++)for (int i=0;i<=bin[j];i++) temp=max(temp,f[i][j]);cout<<ans-temp;return 0;}