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]);
}