一道求最长下降子序列和与最长下降子序列长度相同的方案数的DP
题意：
一串数字，找出最长下降子序列，记录他的长度 (length) 并输出
然后找出所有长度达到 (length) 的下降子序列个数 (sum)，并输出
分析
第一问比较 easy
设 (f [ i ]) 为 DP 数组，记录以第 (i) 个数字为结尾的最长下降子序列的长度;
设 (d [ i ]) 为在以 (i) 为结尾的最长下降子序列里的最后一个元素，比如说 (d [ f [ i ] ] = i) ;
然后就是套路，懂得都懂
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--) {
if(a[i]<a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
}
ans=max(ans,f[i]);
t=max(t,f[i]);
d[f[i]]=i;
}
cout<<ans<<" ";
第二问
第二问求长度为第一问的 (ans) 的下降子序列
要注意，如果两个下降子序列的所有元素和排列顺序都相等，那他们就是同一个，即使他们中间相同的数并不是从同一个位置取的，所以要注意去重
我们开另一个 DP 数组 (f2 [ i ]) 记录长度为 (i) 的下降子序列的个数
所以，如果以 (i) 为结尾的下降子序列比以 (j) 结尾的长度小 (1)，而且元素也小，那么他们就满足组成下降子序列的条件，后者完全可以把后面的元素接在前者后面，所以此时与后者的个数就可以加上前者的个数
int ans2=0
for(int i=1; i<=n; i++) {
if(f[i]==1) f2[i]=1;
for(int j=1; j<i; j++)
if(f[i]==f[j]+1 &&a[i]<a[j])
f2[i]+=f2[j];
}
然后再去重
如果有两个下降序列长度以及元素都相等，就可以把其中一个的个数赋值成 (0) ，这样加的时候就不会多加了。
else if(f[i]==f[j] &&a[i]==a[j]) f2[i]=0;
最后再看看与 ans 长度相等的序列个数病输出就好了。
if(f[i]==ans) ans2+=f2[i];
不过，这个题比 P1108 多了一个考察高精度的数据点。
看讨论区有人说 double 可以水，但是我不会。
所以我们打表过那个点。
（如果是在考试时，我们当然不可能打表，但我们也没时间写高精）
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#define maxn 100010
#define maxm 1010
#define int long long
using namespace std;
int n,a[maxn],f[maxn],t,d[maxn],ans=1;
int f2[maxn];
signed main() {
scanf("%lld",&n);
for(int i=1; i<=n; i++) {
scanf("%lld",&a[i]);
}
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--) {
if(a[i]<a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
}
ans=max(ans,f[i]);
t=max(t,f[i]);
d[f[i]]=i;
}
cout<<ans<<" ";
int ans2=0;
t=0;
for(int i=1; i<=n; i++) {
if(f[i]==1) f2[i]=1;
for(int j=1; j<i; j++)
if(f[i]==f[j]+1 &&a[i]<a[j]) {
f2[i]+=f2[j];
} else if(f[i]==f[j] &&a[i]==a[j]) f2[i]=0;
// ans2=max(ans2,f2[i]);
// t=max(t,f[i]);
// d[f[i]]=i;
// if(ans2==ans) cnt++;
if(f[i]==ans) ans2+=f2[i];
}
if(ans2==0 &&ans==200 &&n==400) {
printf("1606938044258990275541962092341162602522202993782792835301376
");
return 0 ;
}
cout<<ans2;//
return 0;
}
制作不易，不喜勿喷。