Problem G: ZL's Prob.2

Problem G: ZL's Prob.2

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 5
[Submit][Status][Web Board]

Description

< The Phantom of the Opera> is coming soon. 
However we have come across some trouble. 
The price of one ticket is p.  
Now there are n clients waiting out for tickets with exact p money in each of them. However, m other clients are waiting for tickets with undetachable 2p money each.(n>=m) 
What's worse, our ticket center doesn't have change worth money p(in fact we don't have any money at the beginning T T). 
We want you to help us conquer this problem:how many arrangements are there, to make the whole saling progress successfully running? 
(No other people will join in beside those n+m person.)

Input

There are muliply test cases. 
For each test case, 
there is only a line contains the two natural numbers n,m separated by blanks.(n>=m) 
 As you can observe, n and m are both at least 1.

Output

The each output will contain its own answer. 
You may safely assume that each answer fits into a 64-bit unsigned integer.

Sample Input

4 3

2 1

Sample Output

14

2

HINT

分析:

1.与F题大同小异，递归求解+记事本；

#include <cstdio>
#include <iostream>
using namespace std;

long long f[2000][2000];


long long F(long long n,long long m)
{
    if (n<m)return 0;
    if (n==1)return 1;
    if (m==0)return 1;
    if (n==2)return 2;
    if (m==1)return n;
    if (n<2000&&m<2000&&f[n][m]!=0)return f[n][m];
    long long sum=0;
    for (long long i=0;i<=m;i++)
        sum+=F(n-1,i);
    return f[n][m]=sum;
}

int main(void)
{
    long long n,m;
    while (cin>>n>>m)
    {
        cout<<F(n,m)<<endl;
    }
    return 0;
}