Buy the Ticket

【题目地址】HDU1133

【题目大意】有m+n个人在买票，其中m个人拿着50元，n个人拿着100元，每张票50元，售票点没有零钱可以找，输入m，n，问有多少种方式可以使每个人都合理的买到票。

【题目分析】首先，如果m < n，肯定不行（输出0种方案）。

其他情况下：由于m个人拿的都是50元，所以m个人之见可以随便互换位置（有m！种排列），类似的，其余n个人也可以随便互换位置，有n！中排列。持有50元的人和持有100元的人之间有的可以互换位置，有的不可以，那么下面我们就说一下哪些人之见可以互换。假设持有50元的人都是A，持有100元的人都是B。那么排列的第一个元素一定是A，再接着可能是A，也可能是B.......这样我们可以找到递归的规律，然后写出递归函数。

long long temp(int one,int two,int one_sum,int two_sum)     //四个参数依次表示：队列中已经有one人持有50元
                                                            //队列中已经有two人持有100元
                                                            //持有50元和100元的总人数
{
    if(one_sum < two_sum)   //持有50元总人数比持有100元的总人数还少，肯定不行，直接返回0
        return 0;
    if(one < two)   //队列中持有50元的人的数量比持有100元的人的数量少了，肯定不行，返回0
        return 0;
    if(one == one_sum || two == two_sum)    //完成一种分配
        return 1;
    return temp(one+1,two,one_sum,two_sum) + temp(one,two+1,two_sum);   //在队列中再多分配一个持有50元的或持有100元的人

}

上面的递归函数注释已经写的比较明白了，这里我就不再多解释了。

递归函数写起来是比较简单的，但是这样做的话会严重超时！

下面让我们把递归函数改写成for循环。通过数学上的找规律可以发现（其实当时我也找了好半天才突然之间发现的）如下规律：

DP表格

1	1	1	1	1	1
0	1	2	3	4	5
0	0	2	5	9	14
0	0	0	5	14	28

最初我刚画出表格的时候发现的是O（n^3）的for循环写出的dp（代码如下）

long long dp[105][105];
int DP(int one_sum,int two_sum)
{
    mem(dp);<span style="white-space:pre">	</span>//这里是memset函数将dp数组初始化成0
    for(int i = 0; i <= one_sum; i++)
        dp[0][i] = 1ll;

    for(int i = 1; i <= two_sum; i++){
        for(int j = i;j <= one_sum; j++){
            for(int k = 0; k <= i; k++){
                dp[i][j] += dp[k][j-1];
            }
        }
    }
    return 1;
}

调用的时候只需在main函数里面输入：

 DP(m,n);
 ans = dp[n][m];

这两行即可调用。

就在刚刚我写着一篇博客画表格的时候突然之间又发现了一个O（n^2）复杂度的求dp数组的算法（代码如下）:

int DP(int one_sum,int two_sum)
{
    mem(dp);
    for(int i = 0; i <= one_sum; i++)
        dp[0][i] = 1;

    for(int i = 1; i <= two_sum; i++){
        for(int j = i; j <= one_sum; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
}

其实自己想一想很容易理解的，第一个DP做了很多重复的运算。

这样写的话时间复杂度就大大地降了下来，这样做的话，就不会超时了。还有一个问题就是数据太大了，要用到大数进行操作，下面将完整的java代码附上：

import java.math.BigInteger;
import java.util.Scanner;

import javax.management.MXBean;
import javax.swing.SpringLayout.Constraints;

public class Main {
	
	static int MAXN = 105;
	static BigInteger dp[][] = new BigInteger[MAXN][MAXN];
	
	public static void init()	//刚才的DP函数
	//public void init()
	{
	    for(int i = 1; i < MAXN; i++)
	    	for(int j = 0; j < MAXN; j++)
	    		dp[i][j] = BigInteger.valueOf(0); 
	    
	    for(int i = 0; i < MAXN; i++)
	    	dp[0][i] = BigInteger.valueOf(1);
	    		
	    for(int i = 1; i < MAXN; i++){
	        for(int j = i;j < MAXN; j++){
	        	dp[i][j] = dp[i-1][j].add(dp[i][j-1]);
//	            for(int k = 0; k <= i; k++){
//	                dp[i][j] = dp[i][j].add(dp[k][j-1]);
//	            }
	        }
	    }
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner in = new Scanner(System.in);
		int cas = 0;
		
		init();		//为了降低时间复杂度，只需在处理数据之前初始化一下数组dp就可以了，以后每次就可以直接用dp[n][m]
		
		while(true){
			int m,n;
			m = in.nextInt();
			n = in.nextInt();
			if(m + n == 0)
				break;
			
			System.out.println("Test #" + ++cas +":");
			if(n > m){
				System.out.println("0");
				continue;
			}
			BigInteger a = BigInteger.valueOf(1);
			BigInteger b = BigInteger.valueOf(1);
			
			for(int i = 1; i <= m; i++){
				a = a.multiply(BigInteger.valueOf(i));
			}
			for(int i = 1; i <= n; i++){
				b = b.multiply(BigInteger.valueOf(i));
			}
			BigInteger ans;
			ans = a.multiply(b);
			ans = ans.multiply(dp[n][m]);
			
			// ans = dp[n][m];
			
			System.out.println(ans);
		}
	}

}

【回想一下】这道题目运用到了排列组合、java大数(当让你也可以自己用C++或java写大数的这些操作)、数学递推等知识。

首先要将问题分解成 n！ 、 m！和 ans 的乘积，而阶乘操作很好做，剩下的就是运用数学知识来找规律了，用递归函数计算一些简单的值可以来帮助手算找规律，只要找到了这个规律，剩下的就简单了，只需将C++代码改写成java代码，并运用java的大数类就OK了！