首页 > 代码库 > Gym 101334E dp
Gym 101334E dp
分析：
这一题给出的遍历的点的序列，不是树的中序遍历，前序遍历，只要遇到一个节点就打印一个节点。关键点就在，这个序列的首字母和尾字母一定要相同，因为最终都会回到根节点，那么每一个子树也一样。
状态：
d[i][j]表示i至j的状态数
d[i][j]= d[i][j]=(d[i][j]+dp(i,k)*dp(k+1,j-1)%mod)%mod;
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=300+5;const ll mod=1e9;char s[maxn];ll d[maxn][maxn];ll dp(int i,int j){ if(i>j) return 0; if(d[i][j]!=-1) return d[i][j]; if(s[i]!=s[j]) return d[i][j]=0; if(i==j) return d[i][j]=1; d[i][j]=0; for(int k=i;k<j;k++) d[i][j]=(d[i][j]+dp(i,k)*dp(k+1,j-1)%mod)%mod; return d[i][j];}int main(){ freopen("exploring.in","r",stdin); freopen("exploring.out","w",stdout); while(~scanf("%s",s)) { memset(d,-1,sizeof(d)); printf("%I64d\n",dp(0,strlen(s)-1)); } return 0;}
Gym 101334E dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。