[题解] [洛谷P1108] 低价购买

Floyd3265 / 2024-04-25 / 原文

[洛谷P1108] 低价购买

题目描述

给定一个序列，求这个序列的最长严格下降子序列的长度和数量，特别的是如果两个子序列只要每个数都相同，无论原来的位置，都算作同一个子序列。

输入格式

第一行共一个整数 $n(1 \leq n \leq 5000)$ 表示序列长度。

第二行一行 $n$ 个整数，表示序列的每个元素。保证是大小不超过 $2^{16}$ 的正整数。

输出格式

输出共一行两个整数，分别为最大购买次数和拥有最大购买次数的方案数（数据保证 $\leq 2^{31}$ ）。

题解

水蓝题一道。数据范围允许 $O(n ^ 2)$ 复杂度做法，故用最基础的求 $lis$ 的dp方法即可解决第一问。

问题的关键是如何统计出得到 $lis$ 的方案数。自然地可以想到在转移状态的同时记录一下得到当前状态的方案数 $cnt_i$ ，如果找到了更优状态，就把前一个状态的方案数继承过来，如果找到了和当前状态一样优的子状态，就把那个状态的方案数叠加上去即可。

最后剩下的问题就是重复的方案，实际上这中情况仅限于前一个状态对应的最后一位 $a_j$ 相等的情况，不难发现对于两个状态相同的 $j_1, j_2(j_1 < j_2)$ 来说，$j_1$ 的方案是包括在 $j_2$ 中的，因此我们只统计较为靠后的状态的方案数即可，可以通过倒着循环和打标记的方法解决。最后统计答案的时候用类似的方法将所有不同的状态等于 $ans$ 的不相等的方案数累加即可。

AC代码

#include <iostream>
#define int long long
using namespace std;

const int MAXN = 5003;
const int MAXA = 1e5 + 3;

int n, a[MAXN];

int f[MAXN], cnt[MAXN]; // 分别记录长度和方案数
int vis[MAXA]; // 标记是否出现过相同状态

signed main() {
    cin >> n;
    // 输入与初始化
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[i] = f[i] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) vis[a[j]] = 0; // 重置标记
        for (int j = i - 1; j > 0; j--) {
            if (a[i] < a[j]) { // 合法的状态
                if (f[j] + 1 > f[i]) { // 更优的状态转移
                    f[i] = f[j] + 1;
                    // 继承方案数
                    vis[a[j]] = f[i];
                    cnt[i] = cnt[j];
                } else if (f[j] + 1 == f[i]) { // 与当前状态一样优的状态
                    // 累加方案数
                    if (vis[a[j]] != f[i]) cnt[i] += cnt[j]; // 不是相同的状态就累加方案数
                    vis[a[j]] = f[i];
                }
            }
        }
        ans = max(ans, f[i]); // 更新答案
    }
    int anscnt = 0; // 统计方案数
    for (int i = 1; i <= n; i++) vis[a[i]] = false; // 初始化标记
    for (int i = n; i > 0; i--) {
        if (vis[a[i]]) continue; // 如果统计过相同的状态就跳过
        if (f[i] == ans) anscnt += cnt[i], vis[a[i]] = true; // 如果是最优状态就累加到答案里
    }
    // 输出答案
    cout << ans << ' ' << anscnt << '\n';
    return 0;
}