这题有两问，第一问就是最长下降子序列。
对于第二问求最长下降序列的数量，可以通过求第一问的过程解决。设MaxCnt[i]为第i项为末尾中最长下降序列的个数。
对于所有的j(1≤j≤i-1)如果有(s[j]>s[i] 并且 MaxLength[j]+1>MaxLength[i])则MaxCnt[i]=MaxCnt[j]，否则如果(MaxLength[j]+1= =MaxLength[i])可利用加法原理，MaxCnt[i]=MaxCnt[i]+MaxCnt[j]。
考虑到题目中说的不能又重复的序列，我们可以增加一个域Next[i]表示大于i且离i最近的Next[i]使得第Next[i]个数与第i个数相同。如果不存在这样的数则Next[i]=0。这样我们在DP的时候如果出现Next[j]不为0且Next[j]<i可直接跳过。
/*
ID: modengd1
PROB: buylow
LANG:C++
*/
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
int N;
long input[5001];
int dp[5001],next[5001];
int c[5001][500];//MaxCnt数组
int main()
{
freopen("buylow.in","r",stdin);
freopen("buylow.out","w",stdout);
scanf("%d",&N);
for(int i=0;i<N;i++)
scanf("%ld",&input[i]);
input[N]=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<=N;i++)
{
for(int j=0;j<i;j++)
{
if(input[j]>input[i])
{
dp[i]=max(dp[i],dp[j]);
}
}
dp[i]++;
}
memset(next,0,sizeof(next));
for(int i=0;i<=N;i++)
{
for(int j=i+1;j<=N;j++)
{
if(input[i]==input[j])
{
next[i]=j;
break;
}
}
}
memset(c,0,sizeof(c));
for(int i=0;i<=N;i++)
{
for(int j=0;j<i;j++)
{
if((next[j]==0||next[j]>i)&&dp[j]==dp[i]-1&&input[j]>input[i])
{
int k;
for(k=1;k<=c[j][0];k++)
{
c[i][k]+=c[j][k];
c[i][k+1]+=c[i][k]/10;
c[i][k]%=10;
}
while(c[i][k]>=10){c[i][k+1]+=c[i][k]/10;c[i][k]%=10;k++;}
while(c[i][k]==0)k--;
if(k>=c[i][0])c[i][0]=k;
}
}
if(c[i][0]==0)
{
c[i][0]=1;
c[i][1]=1;
}
}
cout<<dp[N]-1<<‘ ‘;
for(int i=c[N][0];i>0;i--)
cout<<c[N][i];
cout<<endl;
return 0;
}
。
原文：http://www.cnblogs.com/modengdubai/p/4851627.html