【HDU5568 BestCoder Round 63 (div1)A】【DP java高精度】sequence2 长度恰好为m的LIS数

本文主要是介绍【HDU5568 BestCoder Round 63 (div1)A】【DP java高精度】sequence2 长度恰好为m的LIS数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定长度为$n$的序列b_ib​i​​，求有多少长度为$k$的本质不同的上升子序列。
设该序列位置为a_1, a_2 ... a_ka​1​​,a​2​​...a​k​​一个序列为上升子序列，当且仅当a_1 < a_2 < ... < a_ka​1​​<a​2​​<...<a​k​​且b_{a_1} < b_{a_2} < ... < b{a_k}b​a​1​​​​<b​a​2​​​​<...<ba​k​​。
本质不同当且仅当两个序列$a$和$A$存在一个$i$使得a_i \neq A_ia​i​​≠A​i​​。

若干组数据（大概$5$组）。
每组数据第一行两个整数$n(1\le n\le 100),k(1\le k\le n)$。
接下来一行$n$个整数b_i(0 \leq b_i \leq 10^{9})b​i​​(0≤b​i​​≤10​9​​)。

对于每组的每个询问，输出一行。

3 2
1 2 2
3 2
1 2 3

2
3

import java.util.*;
import java.math.*;
public class Main 
{final static int N=(int)105;public static int a[]=new int[N];public static int n;public static void main(String[] args) {BigInteger f[][]=new BigInteger[N][N];	Scanner cin=new Scanner(System.in);BigInteger zero=BigInteger.valueOf(0);BigInteger one=BigInteger.valueOf(1);while(cin.hasNext()){int n=cin.nextInt();int m=cin.nextInt();for(int i=1;i<=n;i++)a[i]=cin.nextInt();for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)f[i][j]=zero;}BigInteger ans=zero;for(int i=1;i<=n;i++){f[i][1]=one;int top=Math.min(i,m);for(int j=1;j<i;j++)if(a[j]<a[i]){int topp=Math.min(top,j+1);for(int k=2;k<=topp;k++){f[i][k]=f[i][k].add(f[j][k-1]);}}ans=ans.add(f[i][m]);}System.out.println(ans);}}
}
/*
【trick&&吐槽】
1，如果遇到n=50,m=50，数列呈现{11 22 33 44 55 66 ……}这样的数据，答案显然是2^50。
如果n=50，m=30，答案是2^30*C(50,30)，这个肯定爆掉了LL。于是要同高精度。
2，java的数组一定要养成for循环初始化的好习惯。【题意】
给你一个数组a[]，元素个数最多为n（100），让你求出a[]有多少个长度恰好为m的单调上升子序列。【类型】
DP java大数【分析】
数据组数不多，且n只有100，于是我们只需要想一个O(n^3)时间复杂度的算法，就可以AC这道题。
用f[i][j]表示最后一位位置严格为i，单调上升子序列长度为j的方案数。
那么肯定首先有f[i][1]=1，
然后答案是∑f[i][k]，
至于状态转移方程，则是:f[i][k]=∑f[j][k-1],j<i且a[j]<a[i]。
这样这道题就做完啦~【时间复杂度&&优化】
O(Tn^3)*/

这篇关于【HDU5568 BestCoder Round 63 (div1)A】【DP java高精度】sequence2 长度恰好为m的LIS数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！