Posted on 2010-08-05 13:38
MiYu 閱讀(560)
評論(2) 編輯 收藏 引用 所屬分類:
C/C++ 、
ACM ( DP )
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2151題目描述:
自從見識了平安夜蘋果的漲價后，Lele就在他家門口水平種了一排蘋果樹，共有N棵。
突然Lele發現在左起第P棵樹上(從1開始計數)有一條毛毛蟲。為了看到毛毛蟲變蝴蝶的過程，Lele在蘋果樹旁觀察了很久。雖然沒有看到蝴蝶，但Lele發現了一個規律：每過1分鐘，毛毛蟲會隨機從一棵樹爬到相鄰的一棵樹上。
比如剛開始毛毛蟲在第2棵樹上，過1分鐘后，毛毛蟲可能會在第1棵樹上或者第3棵樹上。如果剛開始時毛毛蟲在第1棵樹上，過1分鐘以后，毛毛蟲一定會在第2棵樹上。
現在告訴你蘋果樹的數目N，以及毛毛剛開始所在的位置P，請問，在M分鐘后，毛毛蟲到達第T棵樹，一共有多少種行走方案數。
int a[M][T] ; 表示蟲子 第 M 分鐘時在 第T顆樹的方法數
狀態轉移方程為 : a[M][T] = a[M-1][T-1] + a[M-1][T + 1];
代碼如下:
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#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;
}