题目描述

原题地址：COGS 洛谷

思路

第一问很简单，最长下降子序列问题，第二问的统计方案数有点意思。

DP方程

DP方程不难得到，设$f(i)$为以$i$结尾的最长下降子序列长度，$g(i)$为结尾为$i$的最优序列数目，则有： $$ g(i)=\sum_{f(j)=f(i)-1} g(j) $$

方案去重

用一个set保存已经累加过的$d(i)$，然后判重即可

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5010;
int f[maxn], g[maxn];
int n, d[maxn];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> d[i];
    d[n + 1] = -(1 << 30);
    for (int i = 1; i <= n + 1; ++i)
    {
        f[i] = g[i] = 1;
        for (int j = 1; j < i; ++j)
            if (d[i] < d[j])
                f[i] = max(f[i], f[j] + 1);
        if (f[i] == 1) continue;
        g[i] = 0;
        set<int> s;
        for (int j = i - 1; j > 0; --j)
            if (d[j] > d[i] && f[j] == f[i] - 1 && !s.count(d[j]))
                g[i] += g[j], s.insert(d[j]);
    }
    cout << f[n + 1] - 1 << ' ' << g[n + 1] << endl;
}