1056: 寻找BOSS
时间限制: 1 Sec 内存限制: 128 MB
提交: 232 解决: 70
[提交][状态][讨论版]
题目描述
战士们，去挑战BOSS吧！BOSS和你共处的区域是一个平面直角坐标系中，你的初始位置在（0,0）处，BOSS的位置在（n,n）处。
邪恶的BOSS对这片区域施加了魔法，即：
（1）你只能向上或向右移动一个单位（不能向左向下走）；（2）y>x所表示的区域是陷阱，你是不能到达的；（3）只能停留在格点上，即点（x,y）,x,y都是整数。
那么你可以有多少种方式到达BOSS的位置？
输入
多组数据
每组数据输入一个正整数n（1<=n<=1000）
输出
输出到达BOSS位置的方案数，对10007取余，并换行
样例输入
1
2
样例输出
1
2
提示
来源
2015西电ACM校赛
//动态规划
#include<stdio.h>
#include<math.h>
#define n 1001
long int dp[n][n];
int main()
{int a,b,i,j;for(i=0;i<n;i++){dp[i][0]=1;} for(i=1;i<n;i++){for(j=1;j<=i;j++){dp[i][j]=dp[i-1][j]%10007+dp[i][j-1]%10007;//敲黑板了，这是重点，过程中每一个结果都要去余数，不然会发生错误}}while(scanf("%d",&a)!=EOF){a=dp[a][a]%10007;printf("%ld\n",a);}return 0;}