hdu-2151
2589 ワード
Worm
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3397 Accepted Submission(s): 2190
Problem Description
クリスマスイブのりんごの値上げを見てから、Leleは彼の家の前にりんごの木を水平に植えて、全部でN本あった.
ふとLeleは左からP本目の木(1から数える)に毛虫がいるのを見つけた.毛虫が蝶になる過程を見るために、Leleはリンゴの木のそばで長い間観察していた.蝶は見えなかったが、Leleは1分ごとに毛虫がランダムに1本の木から隣の木に登るという法則を見つけた.
例えば、最初は2本目の木に毛虫がいましたが、1分後には1本目か3本目の木に毛虫がいる可能性があります.最初に毛虫が1本目の木にいたら、1分後には必ず2本目の木に毛虫がいます.
今あなたにリンゴの木の数Nを教えて、および毛のちょうど位置Pを始めて、お闻きして、M分の后で、毛虫はT本目の木に着いて、全部で何种类の歩く方案の数があります.
Input
この問題には複数のテストが含まれています.ファイルの終了(EOF)まで処理してください.
各グループのテストは1行を占め,4つの正の整数N,P,M,T(意味は問題記述,0
Output
データのセットごとに、1行に合計シナリオ数を出力します.
タイトルデータ保証答えが10^9未満
Sample Input
Sample Output
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3397 Accepted Submission(s): 2190
Problem Description
クリスマスイブのりんごの値上げを見てから、Leleは彼の家の前にりんごの木を水平に植えて、全部でN本あった.
ふとLeleは左からP本目の木(1から数える)に毛虫がいるのを見つけた.毛虫が蝶になる過程を見るために、Leleはリンゴの木のそばで長い間観察していた.蝶は見えなかったが、Leleは1分ごとに毛虫がランダムに1本の木から隣の木に登るという法則を見つけた.
例えば、最初は2本目の木に毛虫がいましたが、1分後には1本目か3本目の木に毛虫がいる可能性があります.最初に毛虫が1本目の木にいたら、1分後には必ず2本目の木に毛虫がいます.
今あなたにリンゴの木の数Nを教えて、および毛のちょうど位置Pを始めて、お闻きして、M分の后で、毛虫はT本目の木に着いて、全部で何种类の歩く方案の数があります.
Input
この問題には複数のテストが含まれています.ファイルの終了(EOF)まで処理してください.
各グループのテストは1行を占め,4つの正の整数N,P,M,T(意味は問題記述,0
Output
データのセットごとに、1行に合計シナリオ数を出力します.
タイトルデータ保証答えが10^9未満
Sample Input
3 2 4 2
3 2 3 2
Sample Output
4 0
Hint
： 2->1->2->1->2 2->1->2->3->2 2->3->2->1->2 2->3->2->3->2
: . , . ( ), .
dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
:
#include<iostream>
using namespace std;
#define MAXN 105
int n,p,m,t;
int dp[MAXN][MAXN];
int dps()
{
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
return dp[m][t];
}
int main()
{
while(cin>>n>>p>>m>>t)
{
memset(dp,0,sizeof(dp));
dp[0][p]=1;
cout<<dps()<<endl;
}
return 0;
}