Hdu 5568 sequence2 高精度 dp

时间:2023-05-23 16:50:50

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);
}
}
}