P2687 逢低吸纳 题解

· · 题解

题目简意

给定一个序列，求其中的最长下降子序列，并给出方案总数。

做法

本题为一道线性 DP 题，难度颇高。 DP 有几个步骤：

  1. 定义状态：线性 DP 的方程一般都是 f_i 为前 i 个元素的最大答案。本题为前 i 个数的最长下降子序列。

  2. 转移方程：这个简单，f_i = \max(f_i,\ f_j + 1)。

  3. 枚举顺序：这步通常挺简单的。看看状态转移方程中哪些东西要先求，比如本题就是 f_j，所以从小到大。

  4. 边界条件：根据定义或者状态转移方程得到。前 1 个数的最长下降子序列就是他自己，f_1 = 1。

  5. 输出：输出答案为 \max(f_1,f_2,\cdots,f_n)。

本题难点：方案统计

定义 cnt 数组为计数数组。分两种情况讨论。

  1. a[i] == a[j] && f[i] == f[j]，此时方案重复！要把cnt[j]清零以去重。
  2. a[i] < a[j] && f[i] == f[j] + 1，那么对于以 a_j 为结尾的最长下降子序列就可以把 a_i 接到后面，并且能保证此时最长下降子序列长度不变，所以 cnt[i] += cnt[j]。

    你以为搞定了吗？

    一交上去，90 分。

原来这题爆 long long……

解决方案：

  1. 面向数据（小心棕名）。
    类似这样：if(n == 400) cout << "200 1606938044258990275541962092341162602522202993782792835301376" << endl;（别的 OJ 上搬过来的，不保证对哈）。

  2. __int128，CSP 给用，但是洛谷神奇 CE。

  3. long double 可以水过，我试了一下失败了，交给你们。

  4. 高精度，最正宗的做法。

    完整代码

    以下是本题代码，珍爱生命，远离抄袭。

Code：

#include<bits/stdc++.h>
using namespace std;

const int N = 5000 + 10;
struct __int256{//定义结构体储存高精度
    int len, num[100];
} g[N], ans;//g 数组就是上文的 cnt
int n, ansnum = 1, a[N], f[N];

__int256 add(__int256 x, __int256 y){
    for(int i=x.len+1;i<=100;i++)   x.num[i] = 0;
    for(int i=y.len+1;i<=100;i++)   y.num[i] = 0;
    __int256 z;
    z.len = max(x.len, y.len);
    memset(z.num, 0, sizeof(z.num));
    for(int i=1;i<=z.len;i++){
        z.num[i] = z.num[i] + x.num[i] + y.num[i];
        z.num[i + 1] = z.num[i] / 10;
        z.num[i] = z.num[i] % 10;
    }
    if(z.num[z.len + 1] > 0)    z.len++;
    return z; 
}//高精加

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)   scanf("%d", &a[i]), f[i] = 1;
    g[1].len = 1, g[1].num[1] = 1;
    ans.len = 1, ans.num[1] = 0;
    for(int i=1;i<=n;i++){
        g[i].len = 1, g[i].num[1] = 0;
        for(int j=1;j<i;j++){
            if(a[i] < a[j]) f[i] = max(f[i], f[j] + 1);
        }//先进行一次转移
        ansnum = max(ansnum, f[i]);//找最后答案
        for(int j=1;j<i;j++){
            if(a[i] == a[j] && f[i] == f[j])    g[j].len = 1, g[j].num[1] = 0;//去重
            else if(a[i] < a[j] && f[i] == f[j] + 1)    g[i] = add(g[i], g[j]);//累加
        }
        if(g[i].len == 1 && g[i].num[1] == 0) g[i].num[1] = 1;
    }
    printf("%d ", ansnum);
    for(int i=1;i<=n;i++)   if(f[i] == ansnum) ans = add(ans, g[i]);//累加方案数
    for(int i=ans.len;i>=1;i--) cout << ans.num[i];//输出方案数
    cout << endl;
    return 0;
}