【题意概述】

　　求一个序列的最长下降子序列的长度及其方案数，若两个子序列的数字是相同的但选取的位置不同，则只算一个。

【题解】

　　Dp，设f[i]为第i个位置为结尾的最长下降子序列的长度，g[i]为第i个位置为结尾的最长下降子序列的方案数。

　　g[i]=max(sigma g[j], 1)   (j<i, f[i]=f[j]+1, a[i]>a[j])

　　同时要注意去重，即如果存在k满足 f[i]=f[k], a[i]=a[k]，则上式中的sigma的j的范围只能是k<j<i

1 #include
     
       2 #include
      
        3 #include
       
         4 #define LL long long 5 #define rg register 6 #define N 200010 7 using namespace std; 8 int n,m,a[N],b[N],f[N],g[N],t[N],mx,cnt; 9 inline int read(){10     int k=0,f=1; char c=getchar();11     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();12     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();13     return k*f;14 }15 inline void add(int x,int y){
   for(;x;x-=x&-x)t[x]=max(t[x],y);}16 inline int query(int x){
   int ret=0;for(;x<=m;x+=x&-x)ret=max(ret,t[x]);return ret;}17 int main(){18     n=read(); 19     for(rg int i=1;i<=n;i++) a[i]=b[i]=read();20     sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1;21     for(rg int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;22 //    for(rg int i=1;i<=n;i++) printf("%d ",a[i]); puts("");23     for(rg int i=1;i<=n;i++){24         f[i]=query(a[i]+1)+1;25         add(a[i],f[i]);26         bool rep=0;27         for(rg int j=1;j
        
         mx) mx=f[i],cnt=g[i];33         else if(f[i]==mx) cnt+=g[i];34     }35     printf("%d %d\n",mx,cnt);36     return 0;37 }