题目描述
“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2162^{16}216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。
这里是某支股票的价格清单：
日期 1,2,3,4,5,6,7,8,9,10,11,12 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8, 9 ,10 ,11, 121,2,3,4,5,6,7,8,9,10,11,12
价格68,69,54,64,68,64,70,67,78,62,98,87 68 ,69 ,54, 64,68 ,64 ,70 ,67 ,78 ,62, 98, 8768,69,54,64,68,64,70,67,78,62,98,87
最优秀的投资者可以购买最多444次股票，可行方案中的一种是：
日期 2,5,6,10 2 , 5 , 6 ,102,5,6,10
价格 69,68,64,62 69, 68 ,64 ,6269,68,64,62
输入输出格式
输入格式：
第1行: N(1≤N≤5000)N(1 \le N \le 5000)N(1≤N≤5000)，股票发行天数
第2行: NNN个数，是每天的股票价格。
输出格式：
两个数:
最大购买次数和拥有最大购买次数的方案数(≤231 \le 2^{31}≤231)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这222种方案被认为是相同的。
输入输出样例
输入样例#1： 复制12 68 69 54 64 68 64 70 67 78 62 98 87输出样例#1： 复制
4 2
题解：
注意这不是LIS，因为它还要求出来方案数，而LIS的DP数组里面只是求出来了以dp[i]以第i个数结尾的LIS，而且这道题还要求我们去重<_>
因此我参考了一下别人的博客https://wjyyy.blog.luogu.org/solution-p1108
- 如果一个数列的第一个数与另一个数列的第一个数相同，那么现在可以判断它们相等，即可以把其中一个删掉（在代码中的处理是t[i]=0t[i]=0t[i]=0）。当不同的数接在它的后面时，又可以将它们判断为两个数列，这是不互相影响的。因为两个数列都可以由这个相等的数列转移而来
- 如果一个数列的第一个数与另一个数列的第一个数不同，那么它们不等，且无论后面添加什么，都不相等，即不删去，则按照普通的判断继续做。
由上面的两点，我们已经把重复的删掉，这样可以防止重复计数。
tiptiptip：本题如果出现在考试中，请不要冒险定义int，因为maxint是231−12^{31}-1231−1，会爆int，这个题暂不做深究
上代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=1000005;
7 int v[maxn],dp[maxn],t[maxn];
8 int main()
9 {
10 int n,m,maxx=0;
11 scanf("%d",&n);
12 m=n;
13 for(int i=1;i<=n;++i)
14 scanf("%d",&v[m--]);
15 for(int i=1;i<=n;++i)
16 {
17 dp[i]=1;
18 for(int j=1;j<i;++j)
19 {
20 if(v[j]<v[i] && dp[j]+1>dp[i])
21 dp[i]=dp[j]+1;
22 }
23 maxx=max(maxx,dp[i]);
24
25 for(int j=1;j<i;++j)
26 {
27 if(dp[j]==dp[i] && v[j]==v[i])
28 t[j]=0;
29 else if(dp[j]+1==dp[i] && v[j]<v[i])
30 t[i]+=t[j];
31 }
32 if(!t[i]) t[i]=1;
33 }
34 int sum=0;
35 for(int i=1;i<=n;++i)
36 {
37 if(dp[i]==maxx)
38 sum+=t[i];
39 }
40 printf("%d %d\n",maxx,sum);
41 }
View Code