非常漂亮的動歸題目，程序裡面的問題都是自己找出來的，做了3天，比較爽。這個題目說白了就是先讓你求最長遞減序列的長度，然後去掉重復的。這個題目關鍵在於去掉重復的。a[i]表示所儲存的元素，然後是dp[i]表示到第i個元素的時候（包括這個元素）的最長遞減序列的長度，count[i]是用來記錄到第i個元素長度是dp[i]的所有結果有多少個。
現在分析去重問題。
這是這組數據的結果，dp[i]的求法就不做贅述了。然後是count[i]，如果dp[i]==1說明了，這個數必然是從1到i最大的那個，也就是count[i]=1。反之必然存在至少為2的count[i]。如果是a[j]>a[i]&&dp[j]+1==dp[i]，這個就能說明這個元素j參與了構成這個最長的下降序列，現在的問題就是如果j元素後面出現了相同的元素怎麼辦，當然結果就是count[i]不加這個j的count[j],因為你在前面已經加進去了。還有一個問題，如果第i號元素前面出現了，我們就直接將前面的那個元素的count賦值為0.具體的看下面的代碼。
[cpp]
?<SPAN style="FONT-SIZE: 18px">#include<iostream>
using namespace std;
int dp[5005];
int a[5005];
int count[5005];
int main()
{
int n,i,j,k,len,p,flag,sum;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>a[i];
dp[1]=1;
memset(count,0,sizeof(count));
count[1]=1;
len=1;
for(i=2;i<=n;i++)
{
dp[i]=1;
for(j=i-1;j>=1;j--)
{
if(a[j]>a[i]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
if(dp[i]>len)
len=dp[i];
}
for(i=2;i<=n;i++)
{
if(dp[i]==1)
count[i]=1;
else {
for(j=i-1;j>=1;j--)
{
if(a[j]==a[i])
count[j]=0;
if(dp[j]+1==dp[i]&&a[i]<a[j])
{
flag=1;
for(k=j+1;k<i;k++)
if(a[k]==a[j])
{
flag=0;
break;
}
if(flag==1)
count[i]+=count[j];
}
}
}
}
sum=0;
for(i=1;i<=n;i++)
if(dp[i]==len)
sum=sum+count[i];
cout<<len<<" "<<sum<<endl;
}
return 0;
}</SPAN>
#include<iostream>
using namespace std;
int dp[5005];
int a[5005];
int count[5005];
int main()
{
int n,i,j,k,len,p,flag,sum;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>a[i];
dp[1]=1;
memset(count,0,sizeof(count));
count[1]=1;
len=1;
for(i=2;i<=n;i++)
{
dp[i]=1;
for(j=i-1;j>=1;j--)
{
if(a[j]>a[i]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
if(dp[i]>len)
len=dp[i];
}
for(i=2;i<=n;i++)
{
if(dp[i]==1)
count[i]=1;
else {
for(j=i-1;j>=1;j--)
{
if(a[j]==a[i])
count[j]=0;
if(dp[j]+1==dp[i]&&a[i]<a[j])
{
flag=1;
for(k=j+1;k<i;k++)
if(a[k]==a[j])
{
flag=0;
break;
}
if(flag==1)
count[i]+=count[j];
}
}
}
}
sum=0;
for(i=1;i<=n;i++)
if(dp[i]==len)
sum=sum+count[i];
cout<<len<<" "<<sum<<endl;
}
return 0;
}
