題目描述
問題描述
蒙提在暴風(fēng)城與鐵爐堡之間的地鐵站中工作了許多年，除了每天抓一些礦道老鼠外，沒有其他的變化。然而最近地鐵站終于要擴(kuò)建了，因?yàn)橘鍌児タ肆私ㄔO(shè)長(zhǎng)距離穿海隧道的技術(shù)難題，矮人們制造的炸藥威力也有了很大的增強(qiáng)。于是，聯(lián)盟決定修建通往諾森德的地鐵。擁有常年的地鐵站工作經(jīng)驗(yàn)的蒙提被派往了新的線路上，他的工作是進(jìn)行地鐵重組。

如上圖，在左邊部分停靠著N節(jié)車廂，從右向左標(biāo)號(hào)依次為1、2、……、N。中間有一個(gè)停車軌道，這個(gè)軌道上最多只能同時(shí)停放P節(jié)車廂。現(xiàn)在需要將左邊軌道上的車廂駛?cè)胗疫叺能壍馈Ｃ抗?jié)車廂必須進(jìn)入一次停車軌道進(jìn)行檢修，然后才能去右邊的軌道。侏儒制造的每節(jié)車廂都有完整的動(dòng)力裝置，不需要依賴車頭的帶動(dòng)。對(duì)于一個(gè)給定的停車軌道的大小P和左邊軌道的車廂的數(shù)目N，蒙提想知道，這些車廂到右邊軌道以后，有多少種不同的排列順序。

輸入
第1行：兩個(gè)整數(shù)N,P。
輸出
第1行：一個(gè)整數(shù)a，為排列順序數(shù)除以4096的余數(shù)。
輸入樣例
3 2

輸出樣例
4

說明
數(shù)據(jù)規(guī)模
對(duì)于70%的數(shù)據(jù)

1 <= N <= 500
1 <= P <= 300

對(duì)于100%的數(shù)據(jù)
1 <= N <= 2000
1 <= P <= 2000

.
.
.
.
.
分析
F[i][j]表示左邊有i個(gè) 棧中有j個(gè)時(shí)的狀態(tài) 最終狀態(tài)為F[0][0]
F[i][j]+=F[i][j+1]+F[i+1][j-1]

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int n,p,f[2010][2010];int main() {scanf("%d%d",&n,&p);memset(f,0,sizeof(f));f[n][0]=1;for (int i=n-1;i>=0;i--)for (int j=min(p,n-i);j>=0;j--){f[i][j]=f[i][j+1]%4096;if (j>=1) f[i][j]+=f[i+1][j-1]%4096;f[i][j]%=4096;}printf("%d",f[0][0]%4096);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/11094921.html

總結(jié)

以上是生活随笔為你收集整理的地铁重组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。