AOJ 2453: Presantation

dp[v]:= v以下の部分木と同じ形が何手で作れるか それぞれに対してコピペに使う根を全探索(サイズの制約で無理なのは無視)して判定。
ハッシュで同じ形を2回以上探索しないようにする。

誰か計算量を解析してください。

#include<stdio.h>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<set>
using namespace std;
typedef unsigned long long wolf;
long long mod=1000000007;
char in[1100000];
int lc[210000];
int rc[210000];
int L[210000];
int R[210000];
wolf rj[610000];
int v[210000];
void dfs(int a){
	v[a]=1;
	if(lc[a]!=-1){
		dfs(lc[a]);
		v[a]+=v[lc[a]];
	}
	if(rc[a]!=-1){
		dfs(rc[a]);
		v[a]+=v[rc[a]];
	}
}
map<wolf,int> dp;
wolf sum[610000];
wolf hash[210000];
int sz;
int chk(int a,int b){
	queue<pair<int,int> >Q;
	Q.push(make_pair(a,b));
	while(Q.size()){
		int at=Q.front().first;
		int cur=Q.front().second;
		Q.pop();
		if(v[cur]==1){
			if(~lc[at]){
				Q.push(make_pair(lc[at],lc[b]));
				Q.push(make_pair(rc[at],rc[b]));
			}
		}else{
			if(v[at]==1)return 0;
			Q.push(make_pair(lc[at],lc[cur]));
			Q.push(make_pair(rc[at],rc[cur]));
		}
	}
	return 1;
}
int calc(int a){
	if(v[a]==3&&~lc[a]&&~rc[a])return 0;
	if(dp.count(hash[a]))return dp[hash[a]];
	
	set<wolf>S;
	int ret=999999999;
	for(int i=a+1;i<sz&&R[i]<R[a];i++){
		if(v[i]==1)continue;
		if(v[a]%(v[i]-1)!=1)continue;
		if(S.count(hash[i]))continue;
		if(!chk(a,i))continue;
		S.insert(hash[i]);
		ret=min(ret,v[a]/(v[i]-1)-1+calc(i));
	}
	return dp[hash[a]]=ret;
}
int main(){
	scanf("%s",in);
	rj[0]=1;
	for(int i=0;i<210000;i++)rc[i]=lc[i]=-1;
	for(int i=1;i<610000;i++)rj[i]=rj[i-1]*mod;
	for(int i=0;in[i];i++){
		sum[i+1]=sum[i]+rj[i]*in[i];
	}
	sz=0;
	stack<int>S;
	S.push(-1);
	for(int i=0;in[i];i++){
		if(in[i]=='('){
			L[sz]=i;
			if(S.top()!=-1){
				if(lc[S.top()]==-1)lc[S.top()]=sz;
				else rc[S.top()]=sz;
			}
			S.push(sz);
			sz++;
		}else{
			R[S.top()]=i;
			S.pop();
		}
	}
	dfs(0);
	for(int i=0;i<sz;i++){
		hash[i]=(sum[R[i]+1]-sum[L[i]])*rj[609999-L[i]];
	}
	printf("%d\n",calc(0));
}