难度：提高+/省选-

题目描述

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

输入输出格式

输入格式:

        第1行: N(1≤N≤5000)，股票发行天数
        第2行: N个数，是每天的股票价格。

输出格式:

        两个数:
        最大购买次数和拥有最大购买次数的方案数(≤231)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候)，这2种方案被认为是相同的。

输入输出样例

Sample input

12
68 69 54 64 68 64 70 67 78 62 98 87

Sample output

4 2

题解

        题目考察线性动态规划/递推，与本材料第四题导弹拦截非常类似(只是多了一个求方案数的步骤)。
        第一问很容易求得，既可以使用O(n2)的经典动态规划思路也可以使用O(nlogn)的二分和贪心思路(详见第四题的加强版本解析)。示例代码给出的是前者。
        下面探讨方案数的求法。
        令f(x)为以下标为x的元素为末尾的最长序列方案数。则dp(x)不为1时有如下的递推关系(不正确的版本):

        初始化f(x)为0，dp(x)为1时直接令f(x)=1。这样答案即为所有dp(x)取到最大值的f(x)之和。
        这里注意到f(x)是很多函数值的和，它们其中重复的组合一定会被重复计算。容易发现，对于一个给定的x，value(x)即是确定的。倘若对于两个k1，k2满足递推式中的条件但是value(k1)≠value(k2)，可以肯定k1和k2这两个序列必不存在相同的序列组合。倘若value(k1)=value(k2)且有k1<k2，可以肯定以k1所指元素为末尾的所有序列都在k2对应的序列集合中。
        综上可知若令S(x)表示以下标为x的元素为末尾的序列组成的集合，那么有:

        这样可知求和对于两个值相同的元素，只加上靠后元素的f值即可。
        但这样仍不宜实现，因为这样需要开一个专门的数组来判断哪些value值已经被访问了。不妨在求每一个f值时就将它之前的与它相同的元素的f值置为0，以此表示该元素已经”失效”了，也就是当求f(x)时若dp(k)=dp(x)且value(k)=value(x)则f(k)=0。这样再结合递推关系就可以求得所有方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstring>

using namespace std;
int dp[5001], op[5001], n;
long long f[5001] = {0};

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i];
        dp[i] = 1;
    }
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++)if (op[j] > op[i])dp[i] = max(dp[j] + 1, dp[i]);
        ans = max(dp[i], ans);
    }
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (dp[j] == dp[i] && op[j] == op[i])f[j] = 0;
            if (dp[j] == dp[i] - 1 && op[j] > op[i])f[i] += f[j];
        }
        if (dp[i] == 1)f[i] = 1;
    }
    long long ans2 = 0;
    for (int i = 1; i <= n; i++)if (dp[i] == ans)ans2 += f[i];
    cout << ans << " " << ans2;
    return 0;
}