0pts暴力求助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[2000005],ans;
bool f[20005][20005];
struct node{
	ll st,ed;
}d[4001][4001];
string s;
int main(){
	cin>>n;
	cin>>s;
	bool flag=0;
	for(int i=1;i<=n;i++){
		a[i]=s[i-1]-'a'+1;
	}
	for(int i=2;i<=n;i++){
		if(a[i-1]==a[i]){
			f[i-1][i]=1;
			ans++;
			d[2][ans].st=i-1;
			d[2][ans].ed=i;
		}
		if(a[i-1]!=a[i])flag=1;
	}
	/*if(!flag){
		for(int i=4;i<n;i+=2){
			ans+=n-i+1;
		}
		cout<<++ans;
		return 0;
	}*/
	int l,r;
	for(int i=4;i<n;i+=2){
		int k=1;
		for(int j=1;j<=n-(i-2)+1;j++){
			if(!d[i-2][j].st||!d[i-2][j].ed)break;
			l=d[i-2][j].st,r=d[i-2][j].ed;
			if(a[l-1]==a[r+1]){
				f[l-1][r+1]=1;
				ans++;
				d[i][k++].st=l-1;
				d[i][k].ed=r+1;
			}
			if(l+i-1<=n){
				if(f[l][r]&&f[r+1][l+i-1]){
					ans++;
					f[l][l+i-1]=1;
					d[i][k++].st=l;
					d[i][k].ed=l+i-1;
				}
			}
		}
	}
	if(f[1][n/2]&&f[n/2+1][n])ans++;
	cout<<ans;
	return 0;
}