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=0;
LL a[maxn],d[maxn],g[maxn];
inline LL read()
{
    LL kr=1,xs=0;
    char ls;
    ls=getchar();
    while(!isdigit(ls))
    {
        if(!(ls^45))
            kr=-1;
        ls=getchar();
    }
    while(isdigit(ls))
    {
        xs=(xs<<1)+(xs<<3)+(ls^48);
        ls=getchar();
    }
    return xs*kr;
}
int main()
{
    n=read();
    for(LL i=1;i<=n;i++)
        a[i]=read();
    for(LL i=1;i<=n;i++)
    {
        for(LL j=1;j<i;j++)
            if(a[i]<a[j]&&d[i]<=d[j])
                d[i]=d[j]+1;
        if(!d[i])
            d[i]=1;
        for(LL j=1;j<i;j++)
            if(d[i]==d[j]&&a[i]==a[j])//判断方案是否重复 
                g[j]=0; 
            else if(d[i]==d[j]+1&&a[i]<a[j])
                g[i]+=g[j];//如果可以接上前面的数列，则继承其方案数 
        if(!g[i])
            g[i]=1;
    }
    for(LL i=1;i<=n;i++)
        maxx=max(maxx,d[i]);//记录最长下降子序列长度 
    for(LL i=1;i<=n;i++)
        if(d[i]==maxx)
            ans+=g[i];//统计最优方案数 
    printf("%lld %lld
",maxx,ans);
return 0;
}