人工智能学习

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

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

人生第一道,完全独立自主(事实上之前也没有不独立自主AC的蓝题)AC的蓝题!

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

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

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

image

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;
}

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

为什么呢?

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

image

就看这张图吧。我们其实可以把等差数列抽象成一个链条的样子,其中一定会出现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大师 - 我人生第一道蓝题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!