洛谷1108 低价购买

双倍经验：洛谷2687 逢低吸纳，全部改成 double 就可以水过。

题意

求最长下降子序列的长度和个数。如果两个序列的值相同，则认为这两个序列相同，只算一个。

序列长度 $N\le 5000$ 。

题解

长度很好求，用 $f[i]$ 表示以 $i$ 结尾的最长下降子序列的长度：

$$f[i] = \max_{j=1}^{i-1} f[j]+1 \ (s[j] > s[i]) \tag{1}$$

但个数就比较麻烦。用 $g[i]$ 表示以 $i$ 结尾的最长下降子序列的个数，比较容易想到：

$$g[i] = \sum_{j=1}^{i-1} g[j] \ (s[j] > s[i],f[i] = f[j]+1) \tag{2}$$

但这样是有锅的。如下面的序列：

$$4,3,2,1,3,2,1,i$$

$g[i]$ 应该是 $1$ ，但按照 $(2)$ 来算就会得到两个相同的序列而 $g[i]=2$ 。

所以需要去重。当两个序列以 $i$ 和 $j$ 结尾，且 $s[i]=s[j],f[i]=f[j]$ ，那么两个序列显然是相同的，这时就可以把 $g[i]=0$ 。

最后答案为

$$\sum_{i=1}^{n} g[i] \ (f[i]=\max f)$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,s[5005],f[5005],g[5005],ans1,ans2;

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<i;j++)
        {
            if (s[j]<=s[i]) continue;
            f[i]=max(f[i],f[j]+1);
        }
        if (!f[i]) f[i]=1;
        ans1=max(ans1,f[i]);
        for (int j=1;j<i;j++)
        {
            if (s[i]==s[j] && f[i]==f[j]) g[j]=0;
            else if (s[i]<s[j] && f[i]==f[j]+1) g[i]+=g[j];
        }
        if (!g[i]) g[i]=1;
    }
    for (int i=1;i<=n;i++)
    {
        if (f[i]<ans1) continue;
        ans2+=g[i];
    }
    return !printf("%d %d",ans1,ans2);
}