洛谷P1108 低价购买

url: https://www.luogu.com.cn/problem/P1108

tag:
动态规划

思路：
问题1就是求最长下降子序列。问题2可以用c[i] 来表示以i为结尾长度为f[i] 的所有下降子序列，然后属性是数量。他可以由倒数第二个数的情况来转移，初始化是当长度为1时数量为1，之后遍历j从1到i，如果满足长度比f[j]大1，然后d[j] > d[i]，就说明可以由c[j] 转移过来，就让c[i] += c[j]，如果长度相同且大小相同，说明之前被计算过了，就让c[i] = 0，最后求答案时判断长度是否为最长，即答案1，如果为最长，则让res2 += c[i]。

代码：

#include <unordered_set>
#include <iostream>
using namespace std;
const int N = 5050;
int d[N], f[N], c[N];
int n, res1, res2;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> d[i];
    for (int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (d[j] > d[i]) f[i] = max(f[i], f[j] + 1);
        }
        res1 = max(res1, f[i]);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (f[i] == 1) c[i] = 1;
        for (int j = 1; j < i; j ++)
        {
            if (f[i] == f[j] + 1 && d[j] > d[i]) c[i] += c[j];
            if (f[i] == f[j] && d[j] == d[i]) c[i] = 0;
        }
        if (f[i] == res1) res2 += c[i];
    }
    cout << res1 << ' ' << res2 << endl;
    return 0;
}