正題

題目鏈接: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

---

題目大意

給出一個歐拉序(只要到達每一個結點就把他加進序列的那種,編號會重復)，求有多少樹的分布。

---

解題思路

我們可以發(fā)現(xiàn)這里每個子樹的字母是連續(xù)的，所以我們可以用fi,jfi,j表示i～ji～j這個區(qū)間組成樹的方案樹。然后每次我們考慮左右各增加一個字母，然后將其重新分割，得出動態(tài)轉移方程。

fl,r=fl+1,r?1+∑l≤r?1,sl=skfl+1,k?1×fk,rfl,r=fl+1,r?1+∑l≤r?1,sl=skfl+1,k?1×fk,r

然后我們可以用記憶化搜索做

---

code

#include<cstdio> #include<cstring> #define BPM 1000000000 using namespace std; char s[310]; int f[310][310],n; int find(int l,int r)//記憶化搜索 {if(l>r) return 0;if(l==r) return 1;if(f[l][r]!=-1) return f[l][r];//記憶化f[l][r]=0;if(s[l]==s[r])for(int k=l+2;k<=r;k++)f[l][r]=(f[l][r]+(long long)find(l+1,k-1)*find(k,r))%BPM;//統(tǒng)計答案return f[l][r];//返回 } int main() {memset(f,-1,sizeof(f));scanf("%s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++) f[i][i]=1;printf("%d",find(1,n)); }

總結

以上是生活随笔為你收集整理的Ch5302-金字塔【区间dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。