HDU5568 sequence2（dp+大数）

题目链接
题意：给你n个数，找出长度是m的上升序列
解答：dp[i][j]：表示以I结尾的长度是j的个数，本题n<=100可以直接暴力转移。
转移是dp[ i ] [ j ] = sum(dp[k] [j-1 ] )（1< = k < i,a[ k ] < a [ i ] ）
如果n比较大的话，可以使用树状数组优化转移，对于大数，就直接java搞起

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
    final static int maxn=1005;
    public static void main(String[] args) {
        BigInteger a[]=new BigInteger[maxn];
        BigInteger dp[][]=new BigInteger[maxn][maxn];
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            int n=cin.nextInt();
            int m=cin.nextInt();

            for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){
                if(j==1)dp[i][j]=BigInteger.ONE;
                else dp[i][j]=BigInteger.ZERO;
            }

            for(int i=1;i<=n;i++){
                long tmp=cin.nextLong();
                a[i]=BigInteger.valueOf(tmp);
            }

            for(int i=1;i<=n;i++){
                for(int j=2;j<=m;j++){
                    for(int k=1;k<i;k++){
                        if(a[k].compareTo(a[i])<0){
                            dp[i][j]=dp[i][j].add(dp[k][j-1]);
                        }
                    }

                }
            }

            BigInteger ans=BigInteger.ZERO;
            for(int i=1;i<=n;i++){
                ans=ans.add(dp[i][m]);
            }
            System.out.println(ans);
        }
    }
}