记录编号	566768	评测结果	AAAAAWAAAA
题目名称	金字塔	最终得分	90
用户昵称	遥时_彼方	是否通过	未通过
代码语言	C++	运行时间	0.287 s
提交时间	2021-11-16 18:35:44	内存使用	1.36 MiB

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long 
using namespace std;
string n;
const ll mod=1e9;
ll f[305][305];
int p[305][305];
ll DP(int l,int r,char st)
{
	if(l>r) return 0;
	if(p[l][r]) 
	{
//		cout<<l+1<<" "<<r+1<<":"<<f[l][r]<<endl;
		return f[l][r];
	}
	if(l==r)
	{
		f[l][r]=1;
		p[l][r]=1;
//		cout<<l+1<<" "<<r+1<<":"<<f[l][r]<<endl;
		return 1;
	}
	ll s1,s2;
	for(int i=l+1;i<r;i++)
	{
		s1=0;
		s2=0;
//		if(n[l]==n[i]) s1+=DP(l+1,i-1,n[l]);
//		if(n[i+1]==n[r]) s2+=DP(i+2,r-1,n[r]);
		if(n[i]==st)
		{
			if(i-l>=2&&n[l]==n[i-1]) s1+=DP(l+1,i-2,n[l]);
			else s1=1;
			s2+=DP(i+1,r,st);
			s1%=mod;
			s2%=mod;
		}
		f[l][r]+=s1*s2;
		f[l][r]%=mod;
	}
	if(n[l]==n[r])
	{
		f[l][r]+=DP(l+1,r-1,n[l]);
		f[l][r]%=mod;
	}
//	cout<<l+1<<" "<<r+1<<":"<<f[l][r]<<endl;
    p[l][r]=1;
	return f[l][r];
}
int main()
{
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.out","w",stdout);
    cin>>n;
    if(n.length()==2) 
    {
    	cout<<0<<endl;
		return 0; 
	} 
    cout<<DP(1,n.length()-2,n[0])<<endl;
//    for(int i=0;i<n.length();i++)
//    {
//    	for(int o=i;o<n.length();o++)
//    	{
//    		cout<<i+1<<":"<<o+1<<":"<<f[i][o]<<endl;
//    	}
//    }
	return 0;
}
//1 2 3 4 5 6 7