洛谷p1108 低价购买

#include<algorithm>
using namespace std;
const int N=5050;
int n,w[N],dp[N],f[N],maxs,ans=0;
int ()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<=n;i++) dp[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if (w[j]>w[i]) dp[i]=max(dp[i],dp[j]+1);
    for(int i=1;i<=n;i++) maxs=max(dp[i],maxs);
    printf("%d ",maxs);
    for(int i=1;i<=n;i++) 
        if (dp[i]==1) f[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
        {
            if (dp[j]+1==dp[i]&&w[i]<w[j]) f[i]+=f[j];
            if (dp[i]==dp[j]&&w[i]==w[j]) f[j]=0;		
        }
    for(int i=1;i<=n;i++)
        if (dp[i]==maxs) ans+=f[i];
    printf("%d",ans);
    return 0;
}