一道簡單但是經典的動態規劃題
描述 打敗萬惡的ghost以后，將軍準備回寢室告訴大伙兒這個消息，沒想到杯具又發生了…
你知道有種鬼叫路鬼嗎？讓人莫名其妙的迷路，將軍就被這種鬼上身了。將軍本來要上樓梯的，但是因為鬼上身，他要不就上一層樓，要不就下一層樓，這個是隨機的，他不能控制自己啦！
假設將軍住在第M樓，因為體力原因，將軍只能上或者下N次樓，剛開始將軍在K樓，假設東6宿舍共有100層。現在問當體力消耗完的時候，將軍剛好回到寢室那一層有多少種可能。
例如：將軍住在5樓，將軍的能上/下5次樓，現在在1樓，
那么將軍將回不到寢室啦，為什么？我也不知道。
輸入有多組測試數據，每組測試數據共一行，為M,N,K（0 < N < 21,0 < M,K < 101）的值，中間以空格分開,分別代表將軍住在第幾層，能移動幾層和剛開始在第幾層； 輸出 對應每一組測試數據，輸出體力消耗完時將軍剛好回到寢室那一層的可能數；
樣例輸入
44 5 41
樣例輸出
5
View Code
#include <iostream> #include<string.h> using namespace std; int main() { int m,n,k,i,j; while(cin>>m>>n>>k) { int dp[105][2];//在連續時間決策過程中，2是為了實現滾動，因為它只有0和1兩個狀態，兩者之間不斷滾動 memset(dp,0,sizeof(dp)); dp[k][0]=1; int d=1; for(i=0;i<n;i++) { for(j=1;j<=100;j++) dp[j][d]=dp[j-1][1-d]+dp[j+1][1-d]; d=1-d; } cout<<dp[m][1-d]<<endl; } return 0; }
posted on 2011-09-23 22:22 More study needed. 閱讀(293) 評論(0) 收藏 舉報
浙公網安備 33010602011771號