话说我好久没写题解了啊(仿佛上午才提交了一个, )。这波,我们先分析一下。

这道题,和P1006传纸条基本相似(如果没刷过洛谷P1006的童鞋,推荐你去刷一刷洛谷P1006传纸条
废话不多说,我们继续讲题。

这是NOIP2000的提高组的第四题。这道题,蒟蒻的我一看都知道这是DP来做。没学DP的童鞋也不要慌,因为,这道题还可以用DFS(不剪枝洛谷对3个样例,蒟蒻不会剪枝,还是老老实实写DP吧~)(虽然题目的数据规模不大,n<=9,但是不会剪枝真的很尴尬)
[我们会有DP、DFS两种解题,但是我重点讲DP( ) ]

我们觉得用DP会比较好

DP方法

),复杂度是N的4次方(笑喷,时间复杂度这么低)
所以我们就用这个方法了!
(没意见1次,没意见2次,成交!)

好,思路有了,就差代码了。
诶,别慌,我们还有东西没讲:f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1])+a[i][j]+a[k][l];
对,就是万年公式

代码(接下来,就是最激动人心的代码公开环节了)

for(int i=1;i<=n;i++){//我居然公开了核心代码??这很不兔子?
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                for(int l=1;l<=n;l++){

                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+a[i][j]+a[k][l];

					if(i==k&&l==j)dp[i][j][k][l]-=a[i][j];

                }
            }
        }
    }

继续,我们解释一下,这是四层循环嵌套(数据不会超时),里面就是这样的,不过多解释~

AC代码(老板,上代码!)

DFS部分

我的DFS和老师的差不多,我的太乱了,于是就粘了一段老师的未剪枝的代码

TLE代码(不会剪枝,不解释)(感谢老师的源码提供)~

本期题解就这样草率结束了,撒个小花花~
希望小伙伴们点个关注,下期我们再会,233333333~拜啦!!

12-13 03:21
查看更多