Description

求一个长度为n的序列a的最长下降子序列的长度,以及这个长度的子序列种数,注意相同的几个子序列只能算作一个子序列.

n<=5000,a[i]不超过long范围

 

Sol

求最长下降子序列的长度: 1.f[i]表示以a[i]结尾的最长下降子序列长度

　　　　　　　　　　　  2.f[i]表示以i结尾的最长下降子序列长度

第一种适用于n比较小的,第二种则适用于n大而a[i]小的,这题显然用第一种吧,而且第一种更方便计数

用num[i]表示以a[i]结尾的长度为f[i]的子序列个数

还需注意的是,这题要去重.

所以更新num[i]数组,j从1循环到i-1时,遇到a[i]==a[j]&&f[i]==f[j]的情况num[i]-=num[j]就好了

因为,在这样的情况中,num[j]所记录的子序列一定也被包含在num[i]中

 

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #define Rg register 5 #define il inline 6 #define db double 7 #define ll long long 8 #define mem(a,b) memset(a,b,sizeof(a)); 9 #define go(i,a,b) for(Rg int i=a;i<=b;++i)10 #define yes(i,a,b) for(Rg int i=a;i>=b;--i)11 using namespace std;12 il int read()13 {14     int x=0,y=1;char c=getchar();15     while(c<'0'||c>'9'){
    if(c=='-')y=-1;c=getchar();}16     while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}17     return x*y;18 }19 const int N=5001;20 int n,ans1,p[N],l[N];//price length21 db ans2,nm[N];//number22 int main()23 {24     n=read();25     go(i,1,n)p[i]=read(),l[i]=1;26     go(i,1,n)27     {28         go(j,1,i-1)if(p[j]>p[i])l[i]=max(l[i],l[j]+1);29         if(l[i]==1)nm[i]=1;30         go(j,1,i-1)31         {32             if(p[i]==p[j]&&l[i]==l[j])nm[i]-=nm[j];33             if(p[j]>p[i]&&l[j]+1==l[i])nm[i]+=nm[j];34         }35     }36     go(i,1,n)if(l[i]>ans1)ans1=l[i];37     go(i,1,n)if(l[i]==ans1)ans2+=nm[i];38     printf("%d %.0lf\n",ans1,ans2);39     return 0;40 }