| 比赛 |
2024国庆练习3 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
金字塔 |
最终得分 |
100 |
| 用户昵称 |
健康铀 |
运行时间 |
0.073 s |
| 代码语言 |
C++ |
内存使用 |
3.61 MiB |
| 提交时间 |
2024-10-06 14:42:40 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long dp[305][305],i,j,k,l,n;
string s;
int main(){
freopen("ZYH.in","r",stdin);
freopen("ZYH.out","w",stdout);
cin>>s;
n = s.size();
for(i = 0;i<n;i++) dp[i][i] = 1;
for(l = 2;l<=n;l++){
for(i = 0;i+l-1<n;i++){
j = i+l-1;
if(s[i]!=s[j]) continue;
for(k = i;k<j;k++) dp[i][j] += (dp[i+1][k-1]*dp[k][j])%1000000000;
dp[i][j]=(dp[i][j]+dp[i+1][j-1])%1000000000;
}
}
cout<<dp[0][n-1]<<"\n";
}