SDUSTOJ 1801 LIS2（最长上升子序列不同值的数量）-白红宇

SDUSTOJ 1801 LIS2（最长上升子序列不同值的数量）

阅读量：6571 次

发布时间：2019-06-24

本文共 1558 字，大约阅读时间需要 5 分钟。

Description

给定一个长度为n的序列(n <= 100) ，给定m(m <= n),求该序列中有多少值不相同的长度为m的严格上升子序列。

Input

先输入一个T，表明下面会有几组数据。

每组数据先输入一个n，m，表明数组大小和上升子序列长度。

下面一行有n个数代表该数组，且 1<=a[i]<=n;

Output

输出为一行，只需输出上述要求的个数(结果对1000000009取余)。

Sample Input

42 21 24 31 2 4 45 41 2 3 5 45 11 1 1 2 2

Sample Output

1122 思路： 还是第三届山科校赛的题目 这个题开两个二维dp数组，第二个是一个延时的dp 也就是没有更新当前状态的dp 再开一个一维数组记一下当前位置数字上次出现的位置 如果上次出现过的话就减掉上一次的dp值去重 dp[i][j]表示以值i为结尾长度为j的最长上升子序列的不同值的数量 具体看代码吧。。

/* ***********************************************Author        :devilCreated Time  :2016/4/26 22:18:57************************************************ */#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 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
                 
                  =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;}