美文网首页
杭电oj-1223-Order Count

杭电oj-1223-Order Count

作者: Fgban | 来源:发表于2019-09-27 19:30 被阅读0次

题目

Problem Description


If we connect 3 numbers with "<" and "=", there are 13 cases:

  1. A=B=C
  2. A=B<C
  3. A<B=C
  4. A<B<C
  5. A<C<B
  6. A=C<B
  7. B<A=C
  8. B<A<C
  9. B<C<A
  10. B=C<A
  11. C<A=B
  12. C<A<B
  13. 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());
        }
 
    }
}

参考内容: http://www.voidcn.com/article/p-wgcqtfaz-zr.html

相关文章

  • 杭电oj-1223-Order Count

    题目 Problem Description If we connect 3 numbers with "<" a...

  • 杭电助手

    杭电助手(服务号hduhelp,订阅号hduhelper)是隶属于杭州电子科技大学党委学工部的校级组织,我们有前端...

  • 杭电2015

    这道题看起来不复杂,但做起来还是挺费工夫的。里面要用很多的循环结构,很容易在些小地方出错。我就是因为那些小问题而搞...

  • 杭电打卡

    这题主要是数学方法求解,其他没什么难度,关键是得出递推公式。 假如第一个和最后一个格子能相同颜色,我们可以很快算出...

  • 杭电oj 第11页 java版答案

    杭电oj 第2000- 2099 题 全答案杭电oj 第十一页答案 具体路径在 src/main/java/com...

  • 杭电ACM1001

    不再更新,杭电ACM的题转到csdn博客

  • 杭电ACM(1013)

  • 二零一七杭电赏梅

    西邻专司花千尊, 东毗惟和草万匀, 纷落梅卿诱草生, 葱绿淡粉妆美人。

  • 杭电-1009 elevator

    这题就是简单的计算,没什么坑直接就ac了,注意更新当前电梯的位置就行。 AC代码

  • 杭电oj 1004

    杭电oj的1004 从这个题开始 我会把自己ac的题目放在简书上方便自己查看 也顺便帮助别人吧

网友评论

      本文标题:杭电oj-1223-Order Count

      本文链接:https://www.haomeiwen.com/subject/uoixyctx.html