P9753
ccf难道不开O2吗，除了注释freopen没动过其他地方

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+1000;
bool can[N][N];
int zy[N][N];
int n;
long long cnt;
char a[N];
signed main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",a+1);
	for(int k=1;k<=n-1;k++){
		for(int i=1;i+k<=n;i++){
			if(k==1){
				if(a[i]==a[i+k]){
					cnt++;can[i][i+k]=true;
				}
			}
			else if(a[i]==a[i+k]){
				if(can[i+1][i+k-1]){
					can[i][i+k]=true;
					cnt++;
				}
			}
			if(!can[i][i+k]&&k!=1){
				for(int j=i+1;j<=i+k-2;j++){
					if(can[i][j]&&can[j+1][i+k]){
						cnt++;
						can[i][i+k]=true;
						break;
					}
				}
			}
		}
	}
	printf("%lld\n",cnt);
	return 0;
}