P1108 [USACO99FALL] 低价购买

题目描述

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

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

$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \textsf{日期} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \cr\hline \textsf{价格} & 68 & 69 & 54 & 64 & 68 & 64 & 70 & 67 & 78 & 62& 98 & 87 \cr\hline \end{array}$

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

$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|}\hline \textsf{日期} & 2 & 5 & 6 & 10 \cr\hline \textsf{价格} & 69 & 68 & 64 & 62 \cr\hline \end{array}$

输入格式

第一行共一个整数 $N\ (1 \le N \le 5000)$，股票发行天数。

第二行一行 N 个整数，是每天的股票价格。保证是大小不超过 $2^{16}$ 的正整数。

输出格式

输出共一行两个整数，分别为最大购买次数和拥有最大购买次数的方案数（数据保证 $ \le 2^{31}）当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候），这 $ 2 种方案被认为是相同的。

输入输出样例 #1

输入 #1

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

输出 #1

4 2

思路

这道题难处在于要求统计拥有最大购买次数的方案，这道题的时间复杂度是O(n^2)(n<=5000),通过观察得出这道题的购买第i支股票是和之前的第j支股票有关的，所以我们可以通过两次循环求出以第i个数字为结尾，最长可以有多少个数字
那么问题来了，比方说{5,4,4,3}就会有两个{5,4,3}，长度为3，数量为2，但是都是同一种方案
为了解决这个问题，我们可以把前缀相同的数字进行去重，那么他们有什么共同点呢，其实就是数字相同且前缀长度相同。
处理之后我们只需要统计每个相同数字的位置，可以统计成方案，也就是数组cnt，最后只要遍历找出拥有最大购买次数的方案数量即可

//Sunshine sunshine ladybugs awake,  
//Clap your hooves and do a little shack.  
#include<bits/stdc++.h>  
#define int long long  
#define endl "\n"  
  
using namespace std;  
  
using PII=pair<int,int> ;  
const int MAXN=100010;  
const int mod=998244353;  
const int INF=0x3f3f3f3f3f3f3f3f;  
  
void solve(){  
    int n;cin>>n;  
    vector<int> a(n);  
    for(auto &x:a)cin>>x;  
        vector<int> len(n,1);  
    for(int i=0;i<n;i++){  
        for(int j=0;j<i;j++){  
            if(a[j]>a[i]&&j<i){  
                len[i]=max(len[i],len[j]+1);  
            }  
        }  
    }  
        int max_len=*max_element(len.begin(),len.end());  
        vector<int> cnt(n,0);  
    for(int i=0;i<n;i++){  
        if(len[i]==1){  
            cnt[i]=1;  
        }  
                for(int j=0;j<i;j++){  
            if(a[j]>a[i]&&len[j]+1==len[i]){  
                cnt[i]+=cnt[j];  
            }else if(a[j]==a[i]&&len[j]==len[i]){  
                cnt[j]=0;  
            }  
        }  
    }  
        int ways=0;  
    for(int i=0;i<n;i++){  
        if(len[i]==max_len){  
            ways+=cnt[i];  
        }  
    }  
        cout<<max_len<<" "<<ways<<endl;  
}  
  
signed main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);  
    //int t;cin>>t;while(t--)  
    solve();  
    return 0;  
}