P2687 题解

· · 题解

首先求出以 a_i 结尾的最长下降子序列的长度 dp_i。有转移：

dp_i=\max_{j<i\land a_j>a_i}dp_j+1

之后计算最长下降子序列的个数 f_i。在转移的过程中，如果从 j 转移到 i 比当前最优解更优，那么将最优解方案数覆盖为 f_j；如果恰好与最优解相同，那么累加方案数即可。

不过这样只能统计 天数序列 不同的方案，而题目要求 元素不同。所以，对于相同的 a_j，只能统计最后一次在 i 之前出现的元素，剩下要全部置 0。

为方便理解给个代码实现：

for (int i = 1; i <= n; i++) {
    f[i] = dp[i] = 1;
    for (int j = 1; j < i; j++) {
        if (a[i] < a[j]) {
            if (dp[i] == dp[j] + 1) f[i] += f[j];
            else if (dp[i] < dp[j] + 1) dp[i] = dp[j] + 1, f[i] = f[j];
        } else if (a[i] == a[j]) f[j] = 0;
    }
    ans = max(ans, dp[i]);
}

结束……了吗？
之前很多题解到这一步就结束了，因为他们认为这个做法的复杂度是 O(n^2)。但是我要告诉你，这个做法是 O(n^3) 的。

为什么呢？先来考虑答案最大是多少：构造每两个数为一组，组内递增，每组的最小值递减。这样可以得出极限答案 2^{n/2}，说明答案的位数是 O(n) 的。在 dp 的过程中需要维护这个高精度，所以要乘上高精加的复杂度。

下面给出两种解决方法：

1. 压位高精

考虑物理上减少答案位数。极限数据下答案大约为 750 位，使用压 8 位高精可以将位数减少到 95，计算量大约为 (5\times10^3)^2\times10^2/4=6\times 10^8，在 2s 的时限下可以通过。

我由于实现垃圾使用的是压 18 位高精。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e3 + 10;
const int MAXM = 42;
const ll BASE = 1e18;

struct Int {
    ll a[MAXM];

    Int(int k = 0) {
        for (int i = MAXM - 1; ~i; i--) a[i] = k % BASE, k /= BASE;
    }

    Int operator + (const Int &rhs) const {
        ll t = 0; Int res = *this;
        for (int i = MAXM - 1; ~i; i--) {
            t += res.a[i] + rhs.a[i];
            res.a[i] = t % BASE, t /= BASE;
        }
        return res;
    }

    friend ostream & operator << (ostream &out, const Int &n) {
        int p = 0;
        for (; p < MAXM && !n.a[p]; p++);
        if (p == MAXM) return out << 0;
        for (out << n.a[p++]; p < MAXM; p++) out << setw(18) << setfill('0') << n.a[p];
        return out;
    }

    Int & operator += (const Int &rhs) { return *this = *this + rhs; }
};

int n, a[MAXN], ans;

int dp[MAXN]; Int f[MAXN], sum;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        f[i] = dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[i] < a[j]) {
                if (dp[i] == dp[j] + 1) f[i] += f[j];
                else if (dp[i] < dp[j] + 1) dp[i] = dp[j] + 1, f[i] = f[j];
            } else if (a[i] == a[j]) f[j] = 0;
        }
        ans = max(ans, dp[i]);
    }
    for (int i = 1; i <= n; i++) if (dp[i] == ans) sum += f[i];
    cout << ans << " " << sum;
}

2. 树状数组

计算最优方案的部分并不需要优化，需要优化的是方案数。

没有“元素不同”要求的情况下，实际上只需要以长度作为下标来记录方案数总和就能解决。有元素不同时，可以使用哈希表来记录 a_j 在 i 之前最后一次出现的位置，每次只会更新一个数的位置，在对应的长度处减去即可。

但是会多算 a_j\le a_i 的情况，所以考虑对于每个值单独开一个树状数组来维护偏序关系。时间复杂度 O(n^2\log n)。

由于树状数组需要离散化，哈希表可以省掉。

代码不放了。