- http://acm.hdu.edu.cn/showproblem.PHP?pid=2151
- Problem Description
自从见识了平安夜苹果的涨价后, Lele 就在他家门口水平种了一排苹果树, 共有 N 棵.
突然 Lele 发现在左起第 P 棵树上 (从 1 开始计数) 有一条毛毛虫. 为了看到毛毛虫变蝴蝶的过程, Lele 在苹果树旁观察了很久. 虽然没有看到蝴蝶, 但 Lele 发现了一个规律: 每过 1 分钟, 毛毛虫会随机从一棵树爬到相邻的一棵树上.
比如刚开始毛毛虫在第 2 棵树上, 过 1 分钟后, 毛毛虫可能会在第 1 棵树上或者第 3 棵树上. 如果刚开始时毛毛虫在第 1 棵树上, 过 1 分钟以后, 毛毛虫一定会在第 2 棵树上.
现在告诉你苹果树的数目 N, 以及毛毛刚开始所在的位置 P, 请问, 在 M 分钟后, 毛毛虫到达第 T 棵树, 一共有多少种行走方案数.
Input
本题目包含多组测试, 请处理到文件结束(EOF).
每组测试占一行, 包括四个正整数 N,P,M,T(含义见题目描述, 0<N,P,M,T<100)
Output
对于每组数据, 在一行里输出一共的方案数.
题目数据保证答案小于 10^9
- Sample Input
- 3 2 4 2
- 3 2 3 2
- Sample Output
- 4
- 0
代码:
- #include <bits/stdc++.h>
- using namespace std;
- int dp[101][101];
- int main() {
- int n, m, p, t;
- while(~scanf("%d%d%d%d", &n, &p, &m, &t)) {
- memset(dp, 0, sizeof(dp));
- dp[0][p] = 1;
- for(int i = 1; i <= m; i ++) {
- for(int j = 1; j <= n; j ++) {
- if(dp[i - 1][j - 1] != 0 || dp[i - 1][j + 1] != 0)
- dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
- }
- }
- printf("%d\n", dp[m][t]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2783813.html