蒟蒻在DP之路上求索着

题目:传送门

题目描述

“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价($2^{16}$范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。

这里是某支股票的价格清单：

日期 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

价格 68, 69, 54, 64, 68, 64, 70, 67, 78, 62, 98, 87

最优秀的投资者可以购买最多4次股票，可行方案中的一种是：

日期 2, 5, 6, 10

价格 69, 68 , 64, 62

数据范围与约定

$N\le 5000, ans\le 2^31$

题解

​ 题目分为两问:1.求出最长下降子序列的长度.2.求出有多少个不同的最长下降子序列.第一问是好做的,只要平凡的$n^2$或者$nlog_2n$的做法就可以求出.关键是第二问.

​ 既然要求有多少不同的最长下降子序列,我们就先来想想什么样的是不同的序列.首先肯定满足对于$i\in [1,n],\exists LIS1[i]\neq LIS2[i]$,即存在一个位置使得两个子序列中这个位置的数不相同.那么我们需要做的就是计数并且去重.但是怎么更直接的判定重复呢?我们需要知道什么样的序列是一样(被重复计算)的.我们设$f[i]$表示以$a[i]$结尾的最长下降子序列的长度.然后我们发现,如果对于两个不同的数$i,j$,有$a[i]=a[j]$而且$f[i]=f[j]$,那么以$a[i],a[j]$结尾的这两个最长下降子序列一定是一样的.因为假设这两个序列中有一个数不相同,那一定会产生大小之分,然后作为”最长”下降子序列,这两个数一定都在这两个序列中,否则不是最长的.而这又和序列中的两个数不相同矛盾,所以假设不成立.

​ 现在我们知道了判断重复的条件,可以去重了.设$g[i]$表示以$a[i]$结尾的最长下降子序列有多少个,那么当我们发现$a[i]=[j]$且$f[i]=f[j]\ \ (j<i)$的时候我们就可让$g[j]$归零.因为$i>j,a[i]=a[j]$,所以能转移到$f[j]$的状态一定能转移到$f[i]$,也就是$g[j]$将被重复计算,我们将其去掉.类似的,当我们发现$f[i]=f[j]+1,a[i]<aj$时,代表从$f[j]$可以转移到$f[i]$,这时我们让$g[i]+=g[j]$即可.

代码:

int n, a[N], f[N], g[N], na[N], cnt, ans;

int main() {
    read(n);
    memset(na, 128, sizeof(na));//采用nlogn求最长下降子序列长度,储存当前序列
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        int l = 1, r = n, pos = 0;
        while (l <= r) {//二分查找第一个>a[i]的数
            int mid = l + r >> 1;
            if (na[mid] > a[i])
                pos = mid, l = mid + 1;
            else r = mid - 1;
        }
        na[pos + 1] = a[i];
        ans = max(f[i] = pos + 1, ans);
        if (f[i] == 1) g[i] = 1;//显然
        for (int j = 1; j < i; ++j)//去重和转移过程
            if (f[i] == f[j] && a[i] == a[j])
                g[j] = 0;
            else if (f[i] == f[j] + 1 && a[i] < a[j])
                g[i] += g[j];
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i)//统计数量
        sum += (f[i] == ans) * g[i];
    cout << ans << " " << sum << endl;
    return 0;
}

——Gensokyo