-
题目描述
-
“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(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
输入
-
第1行: N (1 <= N <= 5000)，股票发行天数第2行: N个数，是每天的股票价格。
输出
-
输出文件仅一行包含两个数:
-
最大购买次数和拥有最大购买次数的方案数(<=2^31)
-
当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。
样例输入
-
12 68 69 54 64 68 64 70 67 78 62 98 87
样例输出
-
4 2
题目思路
-
第一问是求最长下降子序列。
-
第二问是求最长下降子序列的方案数是多少。
-
我们设b[i]为以a[i]结尾的方案数,
-
如果第i个元素小于i之前的某个元素j并且以第i个元素结尾的最长下降子序列也是有以j元素结尾的子序列+1得到的，那么b[i] += b[j]。
-
如果这样的话，6 6 6 1的方案数是3，但是按照题目要求应该输出的是1。
-
因此我们要去除重复的方案。
-
如果第i个元素和第j个元素相同的话，并且以这两个元素结尾的子序列的长度也相同。
-
那么这个时候就要考虑到重复的问题，
-
那么去除第j个元素还是第i个元素呢，即前面的或者是后面的。
-
应该去除前面的，保留后面的，
-
如果i个j之间有个比第i个元素大的，如果去除后面的元素，那么会对结果产生影响，而去除前面的则不会产生影响。
-
题目代码
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define LL long long
#define INF 99999999
using namespace std;int n;
int a[5005];
int dp[5005];
int b[5005];
int main(){scanf("%d",&n);memset(dp,0,sizeof(dp));memset(b,0,sizeof(b));for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}int ans = -1;for(int i = 1 ;i <= n; i++){dp[i] = 1;for(int j = 1; j < i; j++){if(a[i] < a[j])dp[i] = max(dp[i], dp[j]+1);}ans = max(ans, dp[i]);}for(int i = 1; i <= n; i++){if(dp[i] == 1) b[i] = 1;for(int j = 1; j < i; j++){if(a[i] < a[j] && dp[i] == dp[j]+1) b[i] += b[j];if(a[i] == a[j] && dp[i] == dp[j]) b[j] = 0; // 去重 }}int ans2 = 0;for(int i = 0; i <= n; i++){if(dp[i] == ans){ans2 += b[i];}}cout<<ans<<" "<<ans2<<endl;;return 0;
}