HDU 5568 sequence2 区间dp+大数
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5568
题意：
求所有长度为k的严格升序子序列的个数。
题解：
令dp[i][k]表示以i结尾的长度为k的所有严格升序子序列的个数，则有状态转移：dp[i][k]+=dp[j][k-1](其中，arr[i]>arr[j],并且i>j)；
最后答案为dp[1][k]+...dp[n][k]。
代码：
1 import java.util.*; 2 import java.math.*; 3 public class Main { 4 5 public static void main(String args[]){ 6 Scanner cin = new Scanner(System.in); 7 final int maxn=111; 8 int n,k; 9 int[] arr=new int[maxn]; 10 11 while(cin.hasNext()){ 12 n=cin.nextInt(); 13 k=cin.nextInt(); 14 BigInteger[][] dp=new BigInteger[maxn][maxn]; 15 for(int i=1;i<=n;i++){ 16 arr[i]=cin.nextInt(); 17 } 18 for(int i=1;i<=n;i++){ 19 for(int j=1;j<=n;j++) dp[i][j]=BigInteger.ZERO; 20 } 21 for(int i=1;i<=n;i++) dp[i][1]=BigInteger.ONE; 22 for(int kk=2;kk<=k;kk++){ 23 for(int i=1;i<=n;i++){ 24 for(int j=i-1;j>=1;j--){ 25 if(arr[i]>arr[j]){ 26 dp[i][kk]=dp[i][kk].add(dp[j][kk-1]); 27 } 28 } 29 } 30 } 31 BigInteger ans = BigInteger.ZERO; 32 for(int i=1;i<=n;i++) ans=ans.add(dp[i][k]); 33 System.out.println(ans.toString()); 34 } 35 } 36 }