题目描述

“低价购买”这条建议是在奶牛股票市场取得成功的一条规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议：“低价购买；再低价购买”。每次你购买一支股票，你必须用低于你上次购买它的价格购买它。买的次数越多越好！你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将会得到一段时间内一支股票每天的出售价（MAXLONGINT 范围内的正整数），你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一程序计算最大购买次数。
这里是某支股票的价格清单：

日期　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

输入

第一行：N （1〈=N〈=5000），股票发行天数
第二行：N个数，是每天的股票价格。

输出

输出文件仅一行包含两个数：最大购买次数和拥有最大购买次数的方案数（小于等于2当二种方案“看起来是一样”时（就是说它们构成的价格队列一样的时候 ），这2种方案被认为是相同的。

思路

最长不下降子序列加判重，用两个数组分别记录当天能够购买的最大次数和当前数字可以达到的最长不下降子序列长度

#include 
#include 
using namespace std;
int a[5000],b[5000],f[5000];
bool fl[50000];
int main()
{

    int i,j,k,n,max;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);

    b[1]=1;
    f[1]=1;
    for (i=2;i<=n+1;i++)
    {
        max=0;
        f[i]=1;
        for (j=i-1;j>=1;j--)
            if (a[i]max)
                {
                    max=b[j];
                    memset(fl,1,sizeof(fl));
                    fl[a[j]]=false;
                    f[i]=f[j];
                }
                if (b[j]==max&&fl[a[j]]==true)
                {
                    fl[a[j]]=false;
                    f[i]=f[i]+f[j];
                }
            }
        b[i]=max+1;
    }   
    printf("%d %d",b[n+1]-1,f[n+1]);
    return 0;
}