题目描述
“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:
"逢低吸纳,越低越买"
这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。
给定连续的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[5001]; int a[5001]; int a1[110],b1[110],c1[110]; //int num[5001]; struct node{ int len,zu[110]; node operator + (const node x)const{ memset(a1,0,sizeof(a1)); memset(b1,0,sizeof(b1)); memset(c1,0,sizeof(c1)); node res;res.len=0; for(int i=1,j=len;i<=len;i++,j--)a1[i]=zu[j]; for(int i=1,j=x.len;i<=x.len;i++,j--)b1[i]=x.zu[j]; for(int i=1;i<=max(len,x.len);i++){ c1[i]+=a1[i]+b1[i]; c1[i+1]+=c1[i]/10; c1[i]=c1[i]%10; } int l=max(len,x.len); while(c1[l+1]){ l++; c1[l+1]=c1[l]/10; c1[l]=c1[l]%10; } res.len=l; for(int i=1,j=l;i<=l;i++,j--)res.zu[i]=c1[j]; return res; } }num[5001]; int main() { int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<=n;i++) { num[i].len=1; num[i].zu[1]=1; int tmp=1<<30; for(int j = i-1; j>=0;j--) if(a[j]>a[i]) { if(dp[j]>= dp[i]) { tmp = a[j]; dp[i]= dp[j]+1;//最长下降子序列 num[i]= num[j];//路径相同，方案数即相同 } else if (dp[j]+1 == 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=1;i<=num[n].len;i++)printf("%d",num[n].zu[i]); }