HPU第三次积分赛-D：Longest Increasing Subsequence（DP）

时间：2021-09-12 18:41:02

Longest Increasing Subsequence

描述

给出一组长度为n的序列，a1​,a2​,a3​,a4​...an​, 求出这个序列长度为k的严格递增子序列的个数

输入

第一行输入T组数据 T(0≤T≤10)

第二行输入序列大小n(1≤n≤100)，长度k(1≤k≤n)

第三行输入n个数字ai​(0≤ai​≤1e9)

输出

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

输入样例 1 

2

3 2

1 2 2

3 2

1 2 3

输出样例 1

2

3

思路

用dp[i][j]数组记录在i位置，严格递增子序列长度为j的子序列的个数。

状态转移方程 ：HPU第三次积分赛-D：Longest Increasing Subsequence（DP）

在每个i位置j长度的时候遍历前i的位置（不包括第i的位置），去寻找小于a[i]的数字，方案数变成当前i位置长度为j的个数+k位置长度为j-1的方案数

AC代码

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

const double E=exp(1);

const int maxn=1e3+10;

const int mod=1e9+7;

using namespace std;

int dp[maxn][maxn];//表示到第i个位置的递增子序列长度为j的个数

int a[maxn];

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	int t;

	int n,k;

	cin>>t;

	while(t--)

	{

		ms(dp);

		cin>>n>>k;

		for(int i=1;i<=n;i++)

		{

			cin>>a[i];

			dp[i][1]=1;

		}

		for(int i=1;i<=n;i++)

		{

			for(int j=2;j<=i;j++)

			{

				for(int k=1;k<i;k++)

					// 如果a[i]>a[k]，那么dp[i][j]的值加上在k位置的时候长度为j-1的值并取模

					if(a[i]>a[k])

						dp[i][j]=(dp[i][j]%mod+dp[k][j-1]%mod)%mod;

			}

		}

		int ans=0;

		for(int i=1;i<=n;i++)

			ans=(ans+dp[i][k])%mod;

		cout<<ans<<endl;

	}

	return 0;

}

相关文章