河津网站建设,银行需要网站开发人员嘛,自学网络运营要多久,设计类专业哪个就业前景好正题
题目链接:http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5302%20%E9%87%91%E5%AD%97%E5%A1%94 题目大意
给出一个欧拉序(只要到达每一个结点就把他加进序列的那种,编号会重复)#xff0c;求有多…正题
题目链接:http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5302%20%E9%87%91%E5%AD%97%E5%A1%94 题目大意
给出一个欧拉序(只要到达每一个结点就把他加进序列的那种,编号会重复)求有多少树的分布。 解题思路
我们可以发现这里每个子树的字母是连续的所以我们可以用fi,jfi,jf_{i,j}表示i∼ji∼ji\sim j这个区间组成树的方案树。然后每次我们考虑左右各增加一个字母然后将其重新分割得出动态转移方程。
fl,rfl1,r−1∑l≤r−1,slskfl1,k−1×fk,rfl,rfl1,r−1∑l≤r−1,slskfl1,k−1×fk,rf_{l,r}=f_{l+1,r-1}+\sum_{l\leq r-1,s_l=s_k}f_{l+1,k-1}\times f_{k,r}
然后我们可以用记忆化搜索做 code
#includecstdio
#includecstring
#define BPM 1000000000
using namespace std;
char s[310];
int f[310][310],n;
int find(int l,int r)//记忆化搜索
{if(lr) return 0;if(lr) return 1;if(f[l][r]!-1) return f[l][r];//记忆化f[l][r]0;if(s[l]s[r])for(int kl2;kr;k)f[l][r](f[l][r](long long)find(l1,k-1)*find(k,r))%BPM;//统计答案return f[l][r];//返回
}
int main()
{memset(f,-1,sizeof(f));scanf(%s,s1);nstrlen(s1);for(int i1;in;i) f[i][i]1;printf(%d,find(1,n));
}
