Longest Increasing Subsequence————LIS个数

水深无声 2022-05-17 13:04 152阅读 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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode.最长上升子序列(longest-increasing-subsequence)

最长上升子序列(longest-increasing-subsequence) [题解][Link 1] 代码一 class Solution {

Myth丶恋晨/ 2022年12月27日 14:29/ 0 赞/ 52 阅读

相关 LeetCode300——Longest Increasing Subsequence

LeetCode300——Longest Increasing Subsequence 题意：最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没

青旅半醒/ 2022年08月09日 19:30/ 0 赞/ 59 阅读

相关 leetcode 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

今天药忘吃喽~/ 2022年07月28日 01:20/ 0 赞/ 159 阅读

相关 LeetCode673. Number of Longest Increasing Subsequence

A naïve approach of this question would be to generate all the sequences along the way w

冷不防/ 2022年06月07日 00:58/ 0 赞/ 125 阅读

相关 Longest Increasing Subsequence————LIS个数

Longest Increasing Subsequence 描述给出一组长度为nn的序列，a1,a2,a3,a4...an a 1 , a 2 , a 3 , a

水深无声/ 2022年05月17日 13:04/ 0 赞/ 153 阅读

相关 Leetcode：300. Longest Increasing Subsequence（最大增长序列）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

╰+攻爆jí腚メ/ 2022年04月05日 15:48/ 0 赞/ 162 阅读

相关 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

梦里梦外;/ 2022年03月06日 04:34/ 0 赞/ 190 阅读

相关 Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m)，find the longest increasing

本是古典何须时尚/ 2021年12月17日 10:27/ 0 赞/ 144 阅读

相关 SPOJ Another Longest Increasing Subsequence Problem 三维最长链

SPOJ Another Longest Increasing Subsequence Problem 传送门：[https://www.spoj.com/problem

迈不过友情╰/ 2021年12月04日 06:59/ 0 赞/ 152 阅读

相关 300.Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

迈不过友情╰/ 2021年10月01日 04:34/ 0 赞/ 237 阅读