洛谷P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower

时间:2022-10-08 10:27:32

P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower

题目描述

“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者,就要遵守这条秘诀:

"逢低吸纳,越低越买"

这句话的意思是:每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好,看看你最多能按这个规则买几次。

给定连续的N天中每天的股价。你可以在任何一天购买一次股票,但是购买时的股价一定要比你上次购买时的股价低。写一个程序,求出最多能买几次股票。

以下面这个表为例, 某几天的股价是:

天数 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个正整数 (可能分多行) ,第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).

输出格式:

只有一行,输出两个整数:

能够买进股票的天数和长度达到这个值的股票购买方案数量

在计算方案的数量的时候,如果两个方案的股价序列相同,那么这样的两个方案被认为是相同的(只能算做一个方案)。因此,两个不同的天数序列可能产生同一个股价序列,这样只能计算一次。

输入输出样例

输入样例#1:
12
68 69 54 64 68 64 70 67
78 62 98 87
输出样例#1:
4 2
/*
最长下降子序列+方案数,方案数可能很大,要用高精
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<sstream>
using namespace std;
int dp[];
int a[];
int a1[],b1[],c1[];
//int num[5001];
struct node{
int len,zu[];
node operator + (const node x)const{
memset(a1,,sizeof(a1));
memset(b1,,sizeof(b1));
memset(c1,,sizeof(c1));
node res;res.len=;
for(int i=,j=len;i<=len;i++,j--)a1[i]=zu[j];
for(int i=,j=x.len;i<=x.len;i++,j--)b1[i]=x.zu[j];
for(int i=;i<=max(len,x.len);i++){
c1[i]+=a1[i]+b1[i];
c1[i+]+=c1[i]/;
c1[i]=c1[i]%;
}
int l=max(len,x.len);
while(c1[l+]){
l++;
c1[l+]=c1[l]/;
c1[l]=c1[l]%;
}
res.len=l;
for(int i=,j=l;i<=l;i++,j--)res.zu[i]=c1[j];
return res;
}
}num[];
int main()
{
int n;
cin>>n;
for(int i=;i<n;i++)
{
cin>>a[i];
}
for(int i=;i<=n;i++)
{
num[i].len=;
num[i].zu[]=;
int tmp=<<;
for(int j = i-; j>=;j--)
if(a[j]>a[i])
{
if(dp[j]>= dp[i])
{
tmp = a[j];
dp[i]= dp[j]+;//最长下降子序列
num[i]= num[j];//路径相同,方案数即相同
}
else if (dp[j]+ == dp[i]&& a[j]< tmp)//从i前面不同的点到达i点;
{ //如果a[j]> tmp则最长下降子序列的长度就要增加1.
//如果a[j]== tmp 就重复了,需要排除.
tmp = a[j];
num[i]=num[i]+num[j];
}
}
}
printf("%d ",dp[n]);
for(int i=;i<=num[n].len;i++)printf("%d",num[n].zu[i]);
}