……第一眼挺简单-。-
……第二眼不会-。-|||
……考虑DP$f[i][j]$表示 $a$串取了$i$次，$b$串取了$j$次，于是
$f[i-1][j] -> f[i][j]$
$f[i][j-1] -> f[i][j]$
$f[i-1][j-1] -> f[i][j] (a[i]!=b[j])$
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000100
int i,j,k,m,n,x,y,a[N],b[N],rk[N],f[5005][5005],g[N];
int main(){
for(n=read(),i=1;i<=n;++i)a[i]=read(),rk[a[i]]=i;
for(i=1;i<=n;++i)b[i]=read();
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j){
f[i][j]=min(f[i][j],f[i-1][j]+1);
f[i][j]=min(f[i][j],f[i][j-1]+1);
if(a[i]!=b[j])f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
printf("%d\n",f[n][n]);
}
显然数据范围100w是怎么都过不了的-。-
于是得考虑优化Dp
当$n=5$时，且暂不考虑有相同的字符，写出:
$f[i][0]={0,1,2,3,4,5} -> f[i][1]={0,1,2,3,4,5}$
再想到，由于两个串都是排列，于是对于每个j，转移时改变的最多只有1个数，比如：
$A={1,2,3}$
$B={3,2,1}$
$f[i][0]={0,1,2,3}$
$f[i][1]={0,1,2,4}$
于是发现，当不考虑两个字符相同，可以有：
$f[i][j]+1 -> f[i+1][j+1]$
如果相同
$f[i+1][j+1]=Min(f[i][j]+2,f[i][j+1]+1,f[i+1][j]+1)$
然后发现能写出空间复杂度是$O(n)$的$n^2$DP
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000100
int i,j,k,m,n,x,y,a[N],b[N],rk[N],f[N],g[N];
int main(){
for(n=read(),i=1;i<=n;++i)a[i]=read(),rk[a[i]]=i;
for(i=1;i<=n;++i)f[i]=i,b[i]=read();
for(i=1;i<=n;++i){
for(g[0]=i,j=1;j<=n;++j)g[j]=f[j-1]+1;
++g[j=rk[b[i]]];
g[j]=min(g[j],f[j]+1);
g[j]=min(g[j],g[j-1]+1);
for(j=0;j<=n;++j)f[j]=g[j];
}
printf("%d",f[n]);
}
再考虑优化复杂度-。-
可以发现，其实$f[i][j] -> f[i+1][j+1]$这一步转移可以变成f数组+1，然后下标-1，比如：
$//x 表示无用$
$f={x,0,1,2,3} -> f={1,1,2,3,x}$
然后只要用一个支持区间+1，单点修改，单点查询，插入，删除的数据结构维护就行了-。-复杂度$O(n\log n)$
我比较懒，于是就打了个树状数组，复杂度$O(n\log n)$，常数太大，跑得好慢啊！低飞过的-。-
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?-1:*p1++)
inline int read(){
int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 1000100
int i,j,k,m,n,x,y,a[N],b[N],rk[N],f[N<<1],g[N],L,R;
inline void add(int x,int d){++x;for(;x<=R+1;f[x]+=d,x+=x&-x);}
inline int ask(int x){++x;int ret=0;for(;x>=L;ret+=f[x],x-=x&-x);return ret;}
inline int min(int a,int b){return a<b?a:b;}
int main(){
for(n=read(),i=1;i<=n;++i)a[i]=read(),rk[a[i]]=i;
for(L=n+1,R=2*n,i=1;i<=n;++i)add(i+n,1),b[i]=read();
for(i=1;i<=n;++i){
L=n-i+1,R=2*n-i+1;
x=ask(L+rk[b[i]]),add(n-i,i),add(L,-i);
add(L,1),add(R,-1),add(j=n-i+rk[b[i]],1),add(j+1,-1);
int o=ask(j);++x,x=min(ask(j-1)+1,min(x,o));
if(x!=o)add(j,x-o),add(j+1,o-x);
}
printf("%d",ask(n));
}
如果有更优的做法。。求指教
3.1 请教了Claris，果然得到了更优的做法-->传送门
loading...
评论 (0)
