P1004

题意

类似一个比较小的方格(N<=9),有的点是0，有的点有数, A->B的路径经过的点加上该点代表的数，求两次A->B的最大解(最优解)
一个令人恼的问题是两条路径如果有重合点，那么势必回算两次，所以是不合题意的。而先得一次的最大解，并不一定是两次的最优解
这里可以控制两条路径dp[i][j][k][l],(i,j),(k,l)是两条路径，然后可以动态规划做(如何处理重复经过的点呢，可以想一想!!)
据说有些大佬可以用dfs和网络流做
dp可以优化到O(n^2) 不过自己还没掌握

代码

int maxPath(){

    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]=std::max(std::max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),std::max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+mp[i][j]+mp[k][l];

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

                }

            }

        }

    }

    return dp[N][N][N][N];

}

巴特西

luogu p1004

P1004

题意

代码

最新文章

热门文章