P1108 低价购买

传送门

思路：

　　对于第一问很容易看出是求最长下降子序列，N 的暴力就可解决。而第二问是求最优方案数（且不重复），需要判重。可以在求解最长下降子序列的基础上增开一个数组 g ，g[ i ] 表示以 i 结尾，不同的最优方案数。

标程：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<stack>

#include<vector>

#include<queue>

#include<deque>

#include<map>

#include<set>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define maxn 150001

#define INF 0x7f

typedef long long LL;

LL n,maxx=-INF,ans=;

LL a[maxn],d[maxn],g[maxn];

inline LL read()

{

    LL kr=,xs=;

    char ls;

    ls=getchar();

    while(!isdigit(ls))

    {

        if(!(ls^))

            kr=-;

        ls=getchar();

    }

    while(isdigit(ls))

    {

        xs=(xs<<)+(xs<<)+(ls^);

        ls=getchar();

    }

    return xs*kr;

}

int main()

{

    n=read();

    for(LL i=;i<=n;i++)

        a[i]=read();

    for(LL i=;i<=n;i++)

    {

        for(LL j=;j<i;j++)

            if(a[i]<a[j]&&d[i]<=d[j])

                d[i]=d[j]+;

        if(!d[i])

            d[i]=;

        for(LL j=;j<i;j++)

            if(d[i]==d[j]&&a[i]==a[j])//判断方案是否重复

                g[j]=;

            else if(d[i]==d[j]+&&a[i]<a[j])

                g[i]+=g[j];//如果可以接上前面的数列，则继承其方案数

        if(!g[i])

            g[i]=;

    }

    for(LL i=;i<=n;i++)

        maxx=max(maxx,d[i]);//记录最长下降子序列长度

    for(LL i=;i<=n;i++)

        if(d[i]==maxx)

            ans+=g[i];//统计最优方案数

    printf("%lld %lld\n",maxx,ans);

return ;

}