求 hack

答案转化为，操作一次数乘二再加

n

。

令

f_{l,r}

表示初始栈为空，打印

s_{l\dots r}

构成的子串，操作一的最少次数。

转移考虑讨论

r

是用一个新的印版，还是继承上一个

i

满足

s_i=s_r

，打印所用的印版。

如果用一个新的印版，相当于

f_{l,r}=f_{l,r-1}+1

。

如果继承上一个

i

的印版，相当于

s_{(i+1)\dots (r-1)}

所用的印版不能在

i

所用的印版之前，可以认为在打印

s_{(i+1)\dots (r-1)}

时，栈初始是空的。所以转移就是

f_{l,r}=f_{l,i}+f_{i+1,r-1}

。

时间复杂度是

O(Tn^2)

。

但是不知道为什么过不了，不是多测问题且我的答案偏大，求 hack。

代码如下：

CPP

#include <bits/stdc++.h>
using namespace std;

const int maxn=7e3+5;
const int maxc=27;

int T,n;
int lst[maxc],pre[maxn],f[maxn][maxn];
char ch[maxn];

inline void solve(int id){
	scanf("%s",ch+1),n=strlen(ch+1);
	
	for (int i=1;i<=26;i++) lst[i]=0;
	for (int i=1;i<=n;i++){
		pre[i]=lst[ch[i]-'A'+1];
		lst[ch[i]-'A'+1]=i;
	}
	
	for (int i=1;i<=n;i++) f[i][i]=1;
	for (int len=2;len<=n;len++){
		for (int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			int k=pre[r];
			if (k<l) f[l][r]=f[l][r-1]+1;
			else{
				f[l][r]=min(f[l][r-1]+1,f[l][k]+f[k+1][r-1]); 	
			}
		}
	}
	
	printf("Case #%d: %d\n",id,n+2*f[1][n]);
}

int main(){
	scanf("%d",&T);
	for (int i=1;i<=T;i++) solve(i);
		
	return 0;
}

讨论操作

回复

相关推荐

求 hack