【Tai_mount】 算法学习 - 线性动态规划 - luoguP4933大师 - 我人生第一道蓝题

本文主要是介绍【Tai_mount】 算法学习 - 线性动态规划 - luoguP4933大师 - 我人生第一道蓝题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

人生第一道，完全独立自主（事实上之前也没有不独立自主AC的蓝题）AC的蓝题！

大概20210824 22:45-20210825 0:12,初试时间不太记得了，结束时间很准确！

允许我先开心一会儿呜呜呜呜，感觉时间过得好快啊……

一共就提交了两次，一次75，一次AC。

R56881807 AC R56881768 75分

好了，不说废话了，开始

首先看题，这是我从DP题单里找的，所以想DP。

简单来说，给予一个数列，求其子序列中等差数列的个数。0个不算，1个或2个都算，公差不必为正。

在我按照正常逻辑——设立子问题及状态——来思考时。发现无论如何都要标识等差数列的性质……该怎么标识呢？

此刻我家里人都睡觉了，老姐在和男性朋友打和平精英，我爸中间还起床干活，不过在00:00睡觉了。我自己大部分时间在漆黑的客厅里踱步想思路

用两个元素标识！我联想到：这里能出现的等差数列都是由什么确定的，答案是任意两个元素就确定一个等差数列。

接着我们想到，任两个元素确定一个等差数列，那此刻我们往后面找，就能继续找到符合该数列的其他元素，接下来就是在后面找到的元素和前面之间建立联系了。

要注意的是，我们不是要找满足这个等差数列的元素，而是找到那些元素可以真正构成等差数列。比如，3,6确定一个等差数列了，往后找的话，9是可以的，12就不行，虽然12也在这个数列里，但3,6,12显然不是等差数列。

我们从3,6找到9就可以了，然后6,9可以找到12。

一开始我想的是：a,b建立联系，dp[a][b]里存这个等差数列里目前有几个元素了，比如现在就存2，然后找到c令high[c]-high[b]=high[b]-high[a]。这时候dp[b][c]=里转存dp[a][b]的内容然后加1，代表这个数列里已经找到3个了，而dp[a][b]里则存上c。

后来仅仅一点就发现不行，因为这个链条是复杂的，可能会出现high[c1]=high[c2]的情况，你这样就连不过去了。当然我一开始还在想能不能搞个链表什么的都存上，但太麻烦了，一定有更好的方法。

此时我发现我还没想清楚，每次这个数列里多找到一个元素，对这个数列能产生的等差子数列有什么影响。

于是想了想，在纸上画了画，发现，1,2,3,4找到5，那就比1,2,3,4要多4个等差子数列。即4,5/3,4,5/2,3,4,5/1,2,3,4,5。无论什么时候都不可以跳，5不能跳到3只能连到4这样的。显然。

！！！！所以我们dp数组里只要存一下前面已经找到过的元素的个数就行啦？！

ok,所以第一版的是这样的。

int dpfun(){
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(!dp[i][j]) dp[i][j]=1;
            ans+=dp[i][j]; ans%=P;
            for(int k=j+1;k<=n;k++){
                if(high[k]+high[i]==2*high[j]){
                    dp[j][k]=dp[i][j];
                }
            }
        }
    }
    return (ans+n)%P;
}

然后，果不其然，第二个样例就没过。

为什么呢？

想了半天，还是画图很管用。

就看这张图吧。我们其实可以把等差数列抽象成一个链条的样子，其中一定会出现high[3]=high[4]这种情况的。当时我的思路比较混乱，还在把赋值归到点上——事实上dp的意义是边。当时就感觉到5不对劲，3和4都到他身上，我算了算好像应该值是6？（这是很不正确的想法其实）

但至少是发现问题了……哎呦不好描述，我上程序。

int dpfun(){
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(!dp[i][j]) dp[i][j]=1;
            ans+=dp[i][j]; ans%=P;
            for(int k=j+1;k<=n;k++){
                if(high[k]+high[i]==2*high[j]){
                    dp[j][k]+=dp[i][j]+1;
                }
            }
        }
    }
    return (ans+n)%P;
}

然后发现还是不行，本来是答案比我的程序算的多，现在反过来了……（当然第一个样例始终都没问题，这更让我意识到了问题一定就是在这更复杂的链接上）

接下来终于明白了关键，首先dp是标识的上图中边的属性，其次，在第一个程序中算少了的位置是5,6这个边！我第二个程序只是把3,5和4,5这里改多了。

与其说是之前那个“等差数列前面有多少个元素”，更正确的说法是，从任意点出发，走到指定点有多少种路径。你看，之前那个例子不就是1-5,2-5,3-5,4-5嘛。这里也是一样的。如果按照第一个程序，3-5的时候更新5-6，然后4-5的时候又更新5-6，这就给覆盖了，5-6这条边当然算少了。

正确的算法应该是，到5的所有方案都成立，因为再走唯一的那条路都可以到6，另外就是从5开始的额外一种情况。所以是3-4的+4-5的+1。我们在3-5/4-5的时候更新用“+=”，然后每条边刚开始都+1就好了。你看，本来很丑陋的

 if(!dp[i][j]) dp[i][j]=1;

这句话被完美契合进去了。同时，也完美契合了我们之前想到的简单链条的情况。

int dpfun(){
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            dp[i][j]++; dp[i][j]%=P;
            ans+=dp[i][j]; ans%=P;
            for(int k=j+1;k<=n;k++){
                if(high[k]+high[i]==2*high[j]){
                    dp[j][k]+=dp[i][j]; dp[j][k]%=P;
                }
            }
        }
    }
    return (ans+n)%P;
}

这就是最后的dp部分代码了，中间那次75分是因为光在每次ans操作后模P了，此时的dp数组不像刚开始（刚开始的dp数组显然不大于n）,此时需要模P。

最后的最后，我很早就感知到的，之前没说的，1个的情况单算就好，不变的n个，直接加上……这个单个的部分和我们之前的理论明显不对付，肯定就单算了。

有空再写个精简版的吧，这个故意搞很多废话的，主要为了记录自己思考的过程。蛮有意义的！

这篇关于【Tai_mount】 算法学习 - 线性动态规划 - luoguP4933大师 - 我人生第一道蓝题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！