<span>SDUSTOJ 1801 LIS2（最长上升子序列不同值的数量）</span>
Description
给定一个长度为n的序列(n <= 100) ，给定m(m <= n),求该序列中有多少值不相同的长度为m的严格上升子序列。
Input
先输入一个T，表明下面会有几组数据。
每组数据先输入一个n，m，表明数组大小和上升子序列长度。
下面一行有n个数代表该数组，且 1<=a[i]<=n;
每组数据先输入一个n，m，表明数组大小和上升子序列长度。
下面一行有n个数代表该数组，且 1<=a[i]<=n;
Output
输出为一行，只需输出上述要求的个数(结果对1000000009取余)。
Sample Input
4 2 2 1 2 4 3 1 2 4 4 5 4 1 2 3 5 4 5 1 1 1 1 2 2
Sample Output
1 1 2 2
思路：
还是第三届山科校赛的题目
这个题开两个二维dp数组，第二个是一个延时的dp
也就是没有更新当前状态的dp
再开一个一维数组记一下当前位置数字上次出现的位置
如果上次出现过的话就减掉上一次的dp值去重
dp[i][j]表示以值i为结尾长度为j的最长上升子序列的不同值的数量
具体看代码吧。。
/* *********************************************** Author :devil Created Time :2016/4/26 22:18:57 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int N=110; const int mod=1e9+9; LL dp[N][N],dp2[N][N]; int a[N],b[N]; int main() { //freopen("in.txt","r",stdin); int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); memset(dp2,0,sizeof(dp2)); memset(b,-1,sizeof(b)); b[a[1]]=dp[a[1]][1]=1; for(int i=2;i<=n;i++) { dp[a[i]][1]=1; int mi=min(i,m); for(int k=2;k<=mi;k++) { for(int j=1;j<a[i];j++) { dp[a[i]][k]+=dp[j][k-1]; if(dp[a[i]][k]>=mod) dp[a[i]][k]-=mod; } if(b[a[i]]!=-1) { dp[a[i]][k]-=dp2[a[i]][k]; if(dp[a[i]][k]<0) dp[a[i]][k]+=mod; } dp2[a[i]][k]=dp[a[i]][k]; } b[a[i]]=i; } LL ans=0; for(int i=1;i<=n;i++) ans=(ans+dp[i][m])%mod; printf("%lld\n",ans); } return 0; }
蔚来公司氛围 186人发布
查看8道真题和解析