4.3.1 Buy Low, Buy Lower 逢低吸纳

4.3.1 Buy Low, Buy Lower 逢低吸纳

时间: 1ms        内存:64M

描述:

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

"逢低吸纳,越低越买"

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

给定连续的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++).

输出:

只有一行,输出两个整数:
能够买进股票的天数
长度达到这个值的股票购买方案数量
在计算解的数量的时候,如果两个解所组成的字符串相同,那么这样的两个解被认为是相同的(只能算做一个解)。因此,两个不同的购买方案可能产生同一个字符串,这样只能计算一次。

示例输入:

12
68 69 54 64 68 64 70 67
78 62 98 87

示例输出:

4 2

提示:

参考答案(内存最优[4948]):

#include <stdio.h>
#include <string.h>
#define Max(x,y) ((x)>(y)?(x):(y))
#define max_size 5005
#define base 10000
typedef char BOOL;
int arr[max_size],opt[max_size],tot[max_size][205];
BOOL visit[100000];
void add(int a[],int b[],int len)
{
    int i,j;
    for (i=len-1;i>=0;i--)
    {
        a[i]+=b[i];
        a[i-1]+=a[i]/base;
        a[i]%=base;
    }
}
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        int i,j,res1=1,res2;
        memset(tot,0,sizeof(tot));
        for (i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
            opt[i]=1;
        }

        for (i=1;i<n;i++)
        {
            for (j=0;j<i;j++)
                if (opt[i]<opt[j]+1&&arr[j]>arr[i])
                    opt[i]=opt[j]+1;
            res1=Max(res1,opt[i]);
        }

        opt[n]=res1+1;
        arr[n]=-1;

        for (i=0;i<=n;i++)
        {
            if (opt[i]==1)
                tot[i][204]=1;
            else
            {
                memset(visit,1,sizeof(visit));
                for (j=i-1;j>=0;j--)
                {
                    if (opt[j]==opt[i]-1&&arr[j]>arr[i]&&visit[arr[j]])
                    {
                        //tot[i]+=tot[j];
                        add(tot[i],tot[j],205);
                        visit[arr[j]]=0;
                    }
                }
            }
        }
        printf("%d ",res1);
        i=0;
        while (i<205&&tot[n][i]==0) i++;
        printf("%d",tot[n][i++]);
        while (i<205)   printf("%04d",tot[n][i++]);
        printf("\n");
    }
    return 0;
}

参考答案(时间最优[340]):

#include <stdio.h>
#include <string.h>
#define Max(x,y) ((x)>(y)?(x):(y))
#define max_size 5005
#define base 10000
typedef char BOOL;
int arr[max_size],opt[max_size],tot[max_size][205];
BOOL visit[100000];
void add(int a[],int b[],int len)
{
    int i,j;
    for (i=len-1;i>=0;i--)
    {
        a[i]+=b[i];
        a[i-1]+=a[i]/base;
        a[i]%=base;
    }
}
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        int i,j,res1=1,res2;
        memset(tot,0,sizeof(tot));
        for (i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
            opt[i]=1;
        }

        for (i=1;i<n;i++)
        {
            for (j=0;j<i;j++)
                if (opt[i]<opt[j]+1&&arr[j]>arr[i])
                    opt[i]=opt[j]+1;
            res1=Max(res1,opt[i]);
        }

        opt[n]=res1+1;
        arr[n]=-1;

        for (i=0;i<=n;i++)
        {
            if (opt[i]==1)
                tot[i][204]=1;
            else
            {
                memset(visit,1,sizeof(visit));
                for (j=i-1;j>=0;j--)
                {
                    if (opt[j]==opt[i]-1&&arr[j]>arr[i]&&visit[arr[j]])
                    {
                        //tot[i]+=tot[j];
                        add(tot[i],tot[j],205);
                        visit[arr[j]]=0;
                    }
                }
            }
        }
        printf("%d ",res1);
        i=0;
        while (i<205&&tot[n][i]==0) i++;
        printf("%d",tot[n][i++]);
        while (i<205)   printf("%04d",tot[n][i++]);
        printf("\n");
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注