自动搬运

查看原文

来自洛谷，原作者为

	Zhou_yu 这个家伙很懒，但什么都想留下||CZOIer

搬运于2025-08-24 21:40:28，当前版本为作者最后更新于2023-09-23 09:52:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目描述：

P2687 题目传送门

双倍经验

到死不打高精度

所用算法：

1. 求方案数的一道 dp 题。

2. 考察对数据范围的熟悉性。

算法思路：

1. 先推转移方程：

众所周知，动态转移方程就是最长下降子序列的方程， 也就是以自己为子序列结尾，在前面比他数据大的中挑一个作为前一个，并取他们的最大值加 $1$，也就是加上自己。

注意：$f_i$ 的初始值为 $1$，因为自己本身有可能就是最长下降子序列。

所以轻松推出：$f_i=\max(f_i,f_j+1)$

范围及条件：$i>j \wedge a_i<a_j$

2. 统计方案数：

这是这道题的重点！（不考虑高精板子算法）

人人都知道加法原理，所以我们可以将长度为当前长度减一，并且最后一个元素大于目前元素的方案数量加进当前方案数中，让 $anses[i]$ 来存以第 $i$ 个元素为结尾的方案数。

注意：如果出现新的最长下降子序列，要赋初值为 $1$，因为它肯定出现过了。

3. 数据范围：

讨论中，是这个的数据和这个给了我信心来做玄学分析。

只要威力足够大，精度就可以忽略不计！

——by 王站长

long double 就是这样。

事实上，long double 的范围在：$(-1.2 \times 10^{4932},1.2 \times 10^{4932})$，而最大数据甚至小于 $3.8 \times 10^{752}$，虽精度有可能较低，但这数据实是大炮打蚊子，所以不用过多考虑。

蒟蒻の AC 代码

AC 记录

#include <bits/stdc++.h>
#define ld long double
using namespace std;
ld a[5005];
ld f[5005],anses[5005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    ld ma=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    {
    	f[i]=1;//考虑自己本身就是最长下降子序列
        for(int j=1;j<i;j++)
        if(a[i]<a[j])
        f[i]=max(f[i],f[j]+1);//转移方程，方法不再赘述
        ma=max(ma,f[i]);
        //更新答案
        for(int j=1;j<i;j++)
        if(f[i]==f[j]&&a[i]==a[j])anses[j]=0;//如果都是最长，要停止。因为是下降，所以数据等于也要停止
        else if(f[i]==f[j]+1&&a[i]<a[j])anses[i]+=anses[j];//前一个答案可以再用
        if(!anses[i])anses[i]=1;//考虑出现新的最长下降子序列
    }
    ld ans=0;
    for(int i=1;i<=n;i++)
    if(f[i]==ma)
    ans+=anses[i];
    //记得输出时要抹掉小数
    cout<<fixed<<setprecision(0)<<ma<<' '<<ans;
    return 0;
}

总结

前一秒：我今天就算去打高精度也不会用玄学！

后一秒：long double 真香。