正題

題目鏈接:https://www.luogu.com.cn/problem/P1758

---

題目大意

給出一個大小為$n$和一個大小為$m$的棧，每次選擇一個棧彈出棧頂然后記錄這個字母，求所有彈出序列的彈出方案的二次方和。

$1\le n,m\le 500$

---

解題思路

二次方和可以看為取出方案相同的對數。

然后就是很簡單的$dp$了，設$f_{i,j,k}$表示都取出了$i$個，在第一個棧里分開取了$j/k$個，然后滾動。

時間復雜度$O(nm{n}^2)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=510,P=1024523; int n,m,f[N*2][N][N]; char s[N],t[N]; int main() {scanf("%d%d",&n,&m);scanf("%s",s+1);scanf("%s",t+1);f[0][0][0]=1;for(int i=1;i<=n+m;i++)for(int j=0;j<=min(n,i);j++)for(int k=0;k<=min(n,i);k++){f[i&1][j][k]=0;if(s[j]==s[k]&&j&&k)(f[i&1][j][k]+=f[~i&1][j-1][k-1])%=P;if(s[j]==t[i-k]&&j&&i-k)(f[i&1][j][k]+=f[~i&1][j-1][k])%=P;if(t[i-j]==s[k]&&k&&i-j)(f[i&1][j][k]+=f[~i&1][j][k-1])%=P;if(t[i-j]==t[i-k]&&i-j&&i-k)(f[i&1][j][k]+=f[~i&1][j][k])%=P;}printf("%d\n",f[(n+m)&1][n][n]);return 0; }

總結

以上是生活随笔為你收集整理的P1758-[NOI2009]管道取珠【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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