Worm Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other) Total Submission(s) : 17   Accepted Submission(s) : 5 Font: Times New Roman | Verdana | Georgia Font Size: ← → 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 [Hint] 第一组测试中有以下四种走法： 2->1->2->1->2 2->1->2->3->2 2->3->2->1->2 2->3->2->3->2[/Hint] Author Linle Source ACM程序设计期末考试——2008-01-02（3 教417）     #include<stdio.h>__int64 a[110][100];int main(){ int n,p,m,t,i,j; while(scanf("%d%d%d%d",&n,&p,&m,&t)!=EOF) {  for(i=1;i<=n;i++)   for(j=0;j<=m;j++)   {    a[i][j]=0;   }  a[p][0]=1;  for(i=1;i<=m;i++)  {   for(j=1;j<=n;j++)   {    if(j==1)     a[j][i]=a[j+1][i-1];    else if(j==n)     a[j][i]=a[j-1][i-1];    else     a[j][i]=a[j-1][i-1]+a[j+1][i-1];   }  }  printf("%I64d\n",a[t][m]); } return 0;} 

评论