首页 > 专题系列 > Java解POJ > POJ 1633 Gladiators [解题报告] Java
2013
11-10

POJ 1633 Gladiators [解题报告] Java

Gladiators

问题描述 :

In the TV game show Gladiators, the final competition is to run through a steeplechase course. To get some variation, the producer has decided to change the course each week. The course is always built out of m obstacles, all of different heights, placed along a straight line. An obstacle consists of two initially connected platforms which may be separated. Between the two platforms of an obstacle, other higher obstacles may be put. Also, obstacles may be put after one another.



The producer thinks it is most desirable that the results from different weeks may be compared to each other. Therefore, he wants to build courses of similar degree of difficulty.

A proposed measure of difficulty is the number of platforms that are higher than their immediately preceeding platform along the course. Moreover, the leftmost (first) platform of the course always give rise to one point since it is located above the floor. E.g. the course to the right in figure 1 has four points of difficulty.

Your mission is to find out how many ways there are to build a course of a given point of difficulty,from a given number of obstacles.

输入:

On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test scenario consists of one line containing two non negative integers m and k, where m <= 50 is the number of obstacles, and k is the point of difficulty asked for.

输出:

For each test scenario, output one line containing a single positive integer equal to the number of different courses constructable from the m obstacles, amounting to a point of difficulty of exactly k.You may safely assume that the answer is less than 10100.

样例输入:

6
1 0
1 1
2 1
2 2
3 1
3 2

样例输出:

0
1
1
2
1
8

解题代码:

//* @author:alpc12
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    BigInteger[][] dp = new BigInteger[51][51];

    BigInteger go(int n, int y) {
        if (y == 1)
            return BigInteger.ONE;
        if (n < y || y < 1)
            return BigInteger.ZERO;
        if(dp[n][y] != null) {
            return dp[n][y];
        }
        return (dp[n][y] =
            go(n-1, y).multiply(new BigInteger(""+y))
            .add(go(n-1, y-1).multiply(new BigInteger(""+(2*n-y)))));
    }

    void run() {
        Scanner cin = new Scanner(System.in);
        int ntc = cin.nextInt();

        for (int i = 0; i < ntc; ++i) {
            int n = cin.nextInt();
            int y = cin.nextInt();

            System.out.println(go(n, y));
        }
    }

    public static void main(String[] args) {
        new Main().run();

    }

}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。