比普通的LDS要难了一些。

题目描述

“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价($2^{16}$)范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。

这里是某支股票的价格清单：

懒得复制了（ps：LateX数学公式太麻烦）

输入输出格式

输入格式

第一行$N \leq 5000$，股票发行天数
第二行$N$个数，每天的股票价格

输出格式

两个数:
最大购买次数和拥有最大购买次数的方案数( $\leq 2^{31}$)当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这$2$种方案被认为是相同的。

INPUT & OUTPUT’s examples

Input’s eg #1

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

Output’s eg #1

4 2

分析

读完体面后，我们~~显然可以~~看出这是一道线性dp的LDS的，伪模板。

显然，线性dp求LDS是很好写背，状态转移方程如下：

$$dp[i]=std::max(dp[i],dp[j]+1)$$

前提条件if(s[i]<s[j]),i>j。

求长度的时候直接让$Max=std::max(Max,dp[i])$

那么，如何求方案数呢？

首先求出数量：

1
2
3

if(dp[i]==dp[j]+1&&s[i]<s[j]){
    pl[i]+=pl[j];
}

然后去重：

1	if(dp[i]=dp[j]&&s[i]==s[j])pl[i]=0;

代码

// luogu-judger-enable-o2
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<ctime>
#define FOR(i,a,b,c) for(int i=a;i<=b;i+=c)
/* definitions */
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
const int MAXN = 5e3+10;
int n;
int dp[MAXN];
int pl[MAXN];
int shares[MAXN];
int Max,ans;
/* functions */
inline void init(){
    scanf("%d",&n);
    FOR(i,1,n,1)scanf("%d",&shares[i]);
}
int main(int argc,char *argv[]){
    init();
    FOR(i,1,n,1){
        dp[i]=1;
        FOR(j,1,i-1,1){
            if(shares[i]<shares[j]){
                dp[i]=std::max(dp[i],dp[j]+1);
            }
        }
        Max=std::max(Max,dp[i]);
    }
    FOR(i,1,n,1){
        if(dp[i]==1)pl[i]=1;
        FOR(j,1,i-1,1){
            if(dp[i]==dp[j]+1&&shares[i]<shares[j])pl[i]+=pl[j];
            else if(dp[i]==dp[j]&&shares[i]==shares[j])pl[i]=0;
        }
        if(dp[i]==Max)ans+=pl[i];
    }
    printf("%d %d\n",Max,ans);
    return 0;
}

洛谷P1108题解