sequence2
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5568
Description
Given an integer array bi with a length of n, please tell me how many exactly different increasing subsequences.
P.S. A subsequence bai(1≤i≤k) is an increasing subsequence of sequence bi(1≤i≤n) if and only if 1≤a1<a2<...<ak≤n and ba1<ba2<...<bak.
Two sequences ai and bi is exactly different if and only if there exist at least one i and ai≠bi.
Input
Several test cases(about 5)
For each cases, first come 2 integers, n,k(1≤n≤100,1≤k≤n)
Then follows n integers ai(0≤ai≤109)
Output
For each cases, please output an integer in a line as the answer.
Sample Input
3 2
1 2 2
3 2
1 2 3
Sample Output
2
3
HINT
题意
给你n个数,问你有多少个长度为k的上升子序列,需要高精度
题解:
数据范围只有100,所以直接暴力就好了
但是要高精度,所以我们就直接使用java就好了
代码:
import java.util.*;
import java.math.*; public class Main
{
static int n,k;
static int[] a = new int[];
static BigInteger[][] dp = new BigInteger[][];
static BigInteger ans;
public static void main(String[] args)
{
Scanner IN=new Scanner(System.in);
while(IN.hasNext())
{
n = IN.nextInt();
k = IN.nextInt();
for(int i=;i<=n;i++)
a[i] = IN.nextInt();
for(int i=;i<=n+;i++)
for(int j=;j<=n+;j++)
dp[i][j]=BigInteger.ZERO;
ans = BigInteger.ZERO;
for(int i=;i<=n;i++)
{
dp[i][]=BigInteger.ONE;
for(int j=;j<i;j++)
{
if(a[j]<a[i])
{
for(int t=;t<=j+;t++)
{
dp[i][t+]=dp[i][t+].add(dp[j][t]);
}
}
}
}
for(int i=;i<=n;i++)
ans = ans.add(dp[i][k]);
System.out.println(ans);
}
}
}