P2687 [USACO4.3] 逢低吸纳Buy Low, Buy Lower 题解

· · 题解

题目描述：

P2687 题目传送门

双倍经验

到死不打高精度

所用算法：

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

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

算法思路：

  1. 先推转移方程：

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

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

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

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

  1. 统计方案数：

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

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

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

  1. 数据范围：

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

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

——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 真香。