求助,dp被卡
查看原帖
求助,dp被卡
671925
caotianhao楼主2023/9/30 20:58

最后一个点MLE了,代码:

#include<bits/stdc++.h>
using namespace std;
char s[20001],s1[20001];
int t[20001],ans=1,ansl,ansr;
int main(){
	int p=0,p1=0;
	while(scanf("%c",&s[p])!=EOF){
		if(isalpha(s[p])){
			s1[p1]=s[p];
			t[p1]=p;
			if(isupper(s[p])){
				s1[p1]=tolower(s[p]);
			}
			p1++;
		}
		p++;
	}
	int len=strlen(s1);
	int dp[len][len]={};
	for(int i=0;i<p1;i++){
		dp[i][i]=1;
		if(s1[i]==s1[i+1]&&i+1<p1){
			dp[i][i+1]=2;
			ans=2;
		}
	}
	for(int l=3;l<=p1;l++){	
		for(int i=0;i+l-1<p1;i++){
			int j=i+l-1;
			if(s1[i]==s1[j]&&dp[i+1][j-1]!=0){
				dp[i][j]=dp[i+1][j-1]+2;
				ans=l;
			}else{
				dp[i][j]=0;
			}
		}
	}
	cout<<ans<<"\n";
	int maxn=0;
	for(int i=0;i<p1;i++){
		for(int j=0;j<p1;j++){
			if(dp[i][j]>maxn){
				maxn=dp[i][j];
				ansl=i;
				ansr=j;
			}
		}
	}
	int l=t[ansl],r=t[ansr];
	for(int i=l;i<=r;i++){
		cout<<s[i];
	}
	return 0;
}
2023/9/30 20:58
加载中...