2つのサブシーケンス(?識別子)
2030 ワード
Problem 1 2つのサブシーケンス(twosub.pas/c/cpp)
【タイトル説明】
与えられたn個の長さMの01列のシーケンス{a 1,a 2...an}は、2つのサブシーケンス{b 1,b 2...bk}と{c 1,c 2...cm},m+k=nに分けられ、|f(b 1,b 2...bk)|+|f(c 1,c 2...cm)|を最小化する.
f関数は以下のように定義される.
f(空のシーケンス)=空の列f(s)=s f(s 1,s 2)=最小長の接頭辞がs 1に等しく、接尾辞がs 2に等しい文字列がある. f(a1,a2,…,an)=f(f(a1,a2,…,an-1),an).
【入力形式】
1行目の2つの整数n.
次にn行の各行の長さMの01列は、a 1,a 2を表す.an.
【出力形式】
答えを表す整数を出力します.
【サンプル入力】
4 000 111 110 001
【サンプル出力】
8
【データ範囲】
30%のデータに対してn<=20
60%のデータに対してn<=2000
100%のデータに対して、1<=n<=20000,1<=M<=20
この問題は接尾辞DPを使う
f[i][j]は、現在の列挙点でない末尾を表す文字列の末尾がiである
【タイトル説明】
与えられたn個の長さMの01列のシーケンス{a 1,a 2...an}は、2つのサブシーケンス{b 1,b 2...bk}と{c 1,c 2...cm},m+k=nに分けられ、|f(b 1,b 2...bk)|+|f(c 1,c 2...cm)|を最小化する.
f関数は以下のように定義される.
f(空のシーケンス)=空の列f(s)=s f(s 1,s 2)=最小長の接頭辞がs 1に等しく、接尾辞がs 2に等しい文字列がある. f(a1,a2,…,an)=f(f(a1,a2,…,an-1),an).
【入力形式】
1行目の2つの整数n.
次にn行の各行の長さMの01列は、a 1,a 2を表す.an.
【出力形式】
答えを表す整数を出力します.
【サンプル入力】
4 000 111 110 001
【サンプル出力】
8
【データ範囲】
30%のデータに対してn<=20
60%のデータに対してn<=2000
100%のデータに対して、1<=n<=20000,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;
}