Longest Increasing Subsequence———

Longest Increasing Subsequence————LIS个数

水深无声 2022-05-17 13:04 278阅读 0赞

Longest Increasing Subsequence
描述
给出一组长度为nn的序列，a1,a2,a3,a4…an a 1 , a 2 , a 3 , a 4 . . . a n 求出这个序列长度为kk的严格递增子序列的个数

输入
第一行输入T组数据T(0≤T≤10) T ( 0 ≤ T ≤ 10 )
第二行输入序列大小n(1≤n≤100)， n ( 1 ≤ n ≤ 100 ) ，长度k(1≤k≤n) k ( 1 ≤ k ≤ n )
第三行输入n个数字ai(0≤ai≤1e9) a i ( 0 ≤ a i ≤ 1 e 9 )

输出
数据规模很大, 答案请对1e9+7 1 e 9 + 7 取模

输入样例 1
2
3 2
1 2 2
3 2
1 2 3
输出样例 1
2
3

dp[i][j]:=表示以i结尾，长度为j的LIS的数量 d p [ i ] [ j ] := 表示以 i 结尾，长度为 j 的 L I S 的数量

#include<bits/stdc++.h>
using namespace std;
const int MAXN=105;
const int mod=1e9+7;
int a[MAXN];
int dp[MAXN][MAXN];
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i][1]=1;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=i;j++)
                for(int k=1;k<i;k++)
                    if(a[i]>a[k])
                        dp[i][j]=(dp[i][j]+dp[k][j-1])%mod;
        int ans=0;
        for(int i=1;i<=n;i++)
            ans = (ans + dp[i][m])%mod;
        printf("%d\n",ans);
    }
    return 0;
}