Posted on 2010-08-05 13:38
MiYu 閱讀(539)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
C/C++ 、
ACM ( DP )
//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2151題目描述:
自從見識(shí)了平安夜蘋果的漲價(jià)后，Lele就在他家門口水平種了一排蘋果樹，共有N棵。
突然Lele發(fā)現(xiàn)在左起第P棵樹上(從1開始計(jì)數(shù))有一條毛毛蟲。為了看到毛毛蟲變蝴蝶的過程，Lele在蘋果樹旁觀察了很久。雖然沒有看到蝴蝶，但Lele發(fā)現(xiàn)了一個(gè)規(guī)律：每過1分鐘，毛毛蟲會(huì)隨機(jī)從一棵樹爬到相鄰的一棵樹上。
比如剛開始毛毛蟲在第2棵樹上，過1分鐘后，毛毛蟲可能會(huì)在第1棵樹上或者第3棵樹上。如果剛開始時(shí)毛毛蟲在第1棵樹上，過1分鐘以后，毛毛蟲一定會(huì)在第2棵樹上。
現(xiàn)在告訴你蘋果樹的數(shù)目N，以及毛毛剛開始所在的位置P，請(qǐng)問，在M分鐘后，毛毛蟲到達(dá)第T棵樹，一共有多少種行走方案數(shù)。
int a[M][T] ; 表示蟲子 第 M 分鐘時(shí)在 第T顆樹的方法數(shù)
狀態(tài)轉(zhuǎn)移方程為 : a[M][T] = a[M-1][T-1] + a[M-1][T + 1];
代碼如下:
//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
#include<iostream>
int main()
{
int cmt[105][105];
int N,P,M,T;
while ( scanf ( "%d%d%d%d",&N,&P,&M,&T ) != EOF )
{
memset ( cmt, 0, sizeof ( cmt) );
cmt[M][T] = 1;
for ( int i = M - 1; i >= 0; i-- )
{
for ( int j = 1;j <= N; j ++ )
{
if ( j - 1 > 0 )
{
cmt[i][j] += cmt[i+1][j-1];
}
if ( j + 1 <= N )
{
cmt[i][j] += cmt[i+1][j+1];
}
}
}
printf ( "%d\n",cmt[0][P] );
}
return 0;
}