Hust oj 1426 集训队的晚饭(DP)

集训队的晚饭经常是去校外吃盖饭的，一份10元，饭后结账。

结账时，同学们要排队按顺序结账，有n人拿的是20元，m人拿的是10元。但这时发现老板娘没有准备任何零钱，她只能靠收取同学们交的10元钱来找同学们交的20元，而且每个交20元的同学都要求立即找钱。

老板娘想知道到底有多少种不同的收钱顺序。(收相同的面值，不同的人被认为是一样的。例如第一个收A的10元或者B的10元是一样的。)

输入包含多组测试数据。

对于每组测试数据：

第1行，包含两个正整数m,n (1 ≤m,n ≤ 1000)分别代表这拿10元钱的人数和拿20元的人数。

处理到文件结束

对于每组测试数据：

第1行，输出老板娘有多少种不同的收钱顺序。(MOD 1000000007)

3 1

3

设dp[i][j]是有i个10元j个20元时候的方案数，很明显dp[i][j] = dp[i-1][j] + dp[i][j-1]...然后题里说了相同面额只算一种，所以边界就是全是10块的，所以dp[i][0] = 1，要预处理一下，不然会超时

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;const int Maxn = 1005;
const int Mod = 1000000007;
int dp[Maxn][Maxn];
int n,m;void init()
{for(int i=0;i<1003;i++){dp[i][0] = 1;}for(int i=1;i<=1003;i++){for(int j=1;j<=i;j++){dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % Mod;}}
}
int main()
{init();while(~scanf("%d%d",&n,&m)){printf("%d\n",dp[n][m]);}
}