传送门

---

题目大意

求出最长下降子序列的长度以及有多少种不同的最长下降子序列（这里不同指的是某个位置的数不同即可认为不同）

解题思路

观察数据范围，只需要 O ( n 2 ) O(n^2) O(n2) 的做法，但是更快的做法好像没有。

如果没有最长下降子序列种类的限制，可以设 d [ i ] , f [ i ] d[i],f[i] d[i],f[i] 分别代表以位置 i i i 结尾的最长下降子序列的长度和在这个长度下的个数，那么显然需要先求出 d [ i ] d[i] d[i]，然后扫一遍更新 f [ i ] f[i] f[i]：

f [ i ] = m a x ( ∑ j = 1 i − 1 f [ j ] , 1 ) , j < i    a n d    a [ j ] > a [ i ]    a n d    d [ j ] + 1 = d [ i ] f[i] = max(\sum_{j = 1}^{i - 1}f[j], 1),j < i ~~and~~ a[j] > a[i] ~~and~~d[j] + 1 = d[i] f[i]=max(∑j=1i−1​f[j],1),j<i  and  a[j]>a[i]  and  d[j]+1=d[i]

最终答案就是 ∑ i = 1 n f [ i ] , d [ i ] = = m a x l e n \sum_{i=1}^nf[i],d[i] == maxlen ∑i=1n​f[i],d[i]==maxlen

int n;
int a[maxn], d[maxn];
ll f[maxn];

void solve() {
	int ans = 0;
    for(int i = 1; i <= n; i++) {
        d[i] = 1;
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) d[i] = max(d[i], d[j] + 1);
        }
        ans = max(ans, d[i]);
        for(int j = 1; j < i; j++) {
            if(a[j] > a[i] && d[j] + 1 == d[i]) {
                f[i] += f[j];
            }
        }
        if(!f[i]) f[i] = 1;
    }
    ll sum = 0;
    for(int i = 1; i <= n; i++) 
        if(d[i] == ans) sum += f[i];
    cout << ans << " " << sum << endl;
}

但是对于本题来说，需要将最长下降子序列中相同的删去，也就是说在更新 f [ i ] f[i] f[i] 时，将前面 d [ j ] = d [ i ] , f [ j ] = f [ i ] , j < i d[j] = d[i],f[j] = f[i], j < i d[j]=d[i],f[j]=f[i],j<i 的 f [ j ] f[j] f[j] 置为 0，这样后面更新时就只会加上一次 f [ i ] f[i] f[i] 了。

#include <bits/stdc++.h>
using namespace std;
#define ENDL "\n"
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
const int Mod = 1e9 + 7;

int n;
ll a[maxn], d[maxn], f[maxn];

int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        d[i] = 1;
        for(int j = 1; j < i; j++) {
            if(a[j] > a[i])
                d[i] = max(d[i], d[j] + 1);
        }
        ans = max(ans, d[i]);
        for(int j = 1; j < i; j++) {
            if(a[i] == a[j] && d[i] == d[j])
                f[j] = 0;
            else if(a[j] > a[i] && d[j] + 1 == d[i]) {
                f[i] += f[j];
            }
        }
        if(!f[i]) f[i] = 1;
    }
    ll sum = 0;
    for(int i = 1; i <= n; i++) if(d[i] == ans) sum += f[i];
    cout << ans << " " << sum << endl;
    return 0;
}