12
22
2015
0

[bzoj]3072: [Pa2012]Two Cakes

-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%203072.%20--%20[Pa2012]Two%20Cakes.html

……第一眼挺简单-。-

……第二眼不会-。-|||

……考虑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...

Category: bzoj | Tags: DP 平衡树 | Read Count: 702

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com