计算题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个简单的计算，你需要计算f(m,n)，其定义如下：

当m=1时，f(m,n)=n；

当n=1时，f(m,n)=m；

当m>1,n>1时，f(m,n)= f(m-1,n)+ f(m,n-1)

Input

第一行包含一个整数T（1<=T<=100），表示下面的数据组数。

以下T行，其中每组数据有两个整数m，n（1<=m，n<=2000），中间用空格隔开。

Output

对每组输入数据，你需要计算出f(m,n)，并输出。每个结果占一行。

Sample Input

2

1 1

2 3

Sample Output

1

7

m，n数据有点大，直接用类可能会超时，但是后台数据有点弱，所以可以过。（其实输入100，100就会超时）

import java.util.*;public class Main {    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        int a,b,t;        t = cin.nextInt();        while(t-->0)        {            a = cin.nextInt();            b = cin.nextInt();            System.out.println(f(a,b));        }        cin.close();    }    public static int f(int m,int n)    {        if(m==1)            return n;        if(n==1)            return m;        return f(m-1,n) + f(m,n-1);    }}

所以用数组存储的方式来做。

结果发现了一个特别坑的问题，计算结果哪怕开long也会爆……

iimport java.util.*;public class Main {    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        int a,b,t,i,j;        long f[][] = new long [2050][2050];        for(j=0;j<=2000;j++)            f[1][j] = j;        for(i=0;i<=2000;i++)            f[i][1] = i;        for(i=2;i<=2000;i++)            for(j=2;j<=2000;j++)                f[i][j] = f[i-1][j] + f[i][j-1];        t = cin.nextInt();        while(t-->0)        {            a = cin.nextInt();            b = cin.nextInt();            System.out.println(f[a][b]);        }        cin.close();    }}