杭电oj-1223-Order Count
题目
Problem Description
If we connect 3 numbers with "<" and "=", there are 13 cases:
- A=B=C
- A=B<C
- A<B=C
- A<B<C
- A<C<B
- A=C<B
- B<A=C
- B<A<C
- B<C<A
- B=C<A
- C<A=B
- C<A<B
- C<B<A
If we connect n numbers with "<" and "=", how many cases then?
Input
The input starts with a positive integer P(0<P<1000) which indicates the number of test cases. Then on the following P lines, each line consists of a positive integer n(1<=n<=50) which indicates the amount of numbers to be connected.
Output
For each input n, you should output the amount of cases in a single line.
Sample Input
2
1
3
Sample Output
1
13
Huge input, scanf is recommended.
解题思路
首先做个定义，n字母中若有r个小于符号，而其他都为等于，认为有r+1个相等类。比如A=B<C<D，有2个小于符号，则有3个相等类。
本题中是要根据输入的n个字母，判断有多少种只包含=和<的序列。容易想到的是n个字母最多可以有n个相等类，最少1个相等类，所以可以计算出n个字母下不同相等类下的序列数，再求和得到总的结果数。
而对于n个字母的某一种相等类数下，我们可以思考是否可以用n-1个字母的情况推导呢？答案当然是肯定的。
假设需要求解i个字母，相等类数为j的序列数。我们考虑i-1个字母的情况，因为当添加一个字母时，可以添加的符号只有“=”和“<”，如果i-1个字母变到i个字母添加的是“=”的话（不管添加到i-1个字母的情况中j个相等类的任何一个类），它的相等类数j是不变的，即i个字母，j个相等类的情况是由i-1个字母j个相等类得到的；如果i-1个字母变到i个字母添加的是“<”的话，那么相等类的个数是加1了的，即i个字母，j个相等类的情况是由i-1个字母j-1个相等类得到的。因为等于和小于两种情况都要包括，所以对两种情况实行加法。当然符号确定了之后，还需要确定字母插入到哪一个相等类，由于两种情况都会确定j个相等类，所以字母的选择有j中，所以再将加法过后的数乘上j即得i个字母，相等类数为j的序列数。
由以上推理，便可以使用动态规划求解。从推理中得到其递推公式如下：
num[i][j] = ( num[i-1][j] + num[i-1][j - 1] ) * j
（i，j代表i个字母j个相等类。）
还有一点则是本题需要使用大数，一般的整型无法满足题目的要求。
java示例代码
import java.io.*;
import java.util.*;
import java.math.*;
public class Main_AOJ440
{
private static BigInteger[][] num=new BigInteger[55][55];
public static void main(String[] args)
{
Scanner cin = new Scanner(new BufferedInputStream(System.in));
//初始置零
for(int i=0;i<=50;++i)
for(int j=0;j<=50;++j)
num[i][j]=BigInteger.ZERO;
//1，1对应值初始化
num[1][1]=BigInteger.valueOf(1);
//使用递推公式求解打表
for(int i=2;i<=50;++i)
for(int j=1;j<=i;++j)
num[i][j]=num[i-1][j].add(num[i-1][j-1]).multiply(BigInteger.valueOf(j));
int temp=cin.nextInt();
//将每个相等类j下的序列数相加得到结果数
for(;(temp--)!=0;)
{
int n=cin.nextInt();
BigInteger big=BigInteger.ZERO;
for(int i=1;i<=n;i++)
big=big.add(num[n][i]);
System.out.println(big.toString());
}
}
}
