正題

---

題目大意

n個東西依次進入一個容量為p的棧，求出棧的序列數量。

---

解題思路

設$f_{i,j}$表示$i$個已經進過棧了(不管還有沒有出)，$j$個還在棧里。

首先是將現在這個進棧$f_{i?1,j?1}$，然后是出棧$f_{i,j+1}$

方程$$f_{i,j}=f_{i?1,j?1}+f_{i,j+1}(j\le p)$$

---

$code$

#include<cstdio> #include<algorithm> using namespace std; const int N=2010,XJQ=4096; int n,p,f[N][N]; int main() {scanf("%d%d",&n,&p);f[1][1]=f[1][0]=1;for(int i=2;i<=n;i++){for(int j=p;j>=0;j--)if(j==0) f[i][j]=f[i][j+1]%XJQ;else f[i][j]=(f[i-1][j-1]+f[i][j+1])%XJQ;}printf("%d",f[n][0]); }

總結

以上是生活随笔為你收集整理的nssl1318-地铁重组【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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