《算法竞赛进阶指南》0x51线性DP 传纸条

2021-04-07 13:26

阅读：650

标签：线性dp name str pre main 计算 cout end 枚举

题目要求：给一个n*m的矩阵，求从左上角到右下角的两条路径，使得两条路径上的值只和最大。从左上角往右下角走的时候只能向下或者向右。

在这个问题中阶段就是步数，步数与坐标点的横纵坐标之和相差一个常数，所以可以通过坐标只和以及两个点的横坐标来确定当前的状态集合。此时通过一个点的所有入边更新一个点即可。一共有四种状态，代价可以先计算出来。其中坐标枚举的范围要综合考虑横纵坐标的范围。

代码：

#include
#include
#includestring.h>
using namespace std;
const int maxn = 56;
int n,m;
int w[maxn][maxn];
int f[maxn1][maxn][maxn];
int main(){
    cin>>n>>m;
    for(int i=1;i)
        for(int j=1;j)
            cin>>w[i][j];
    
    for(int k=2;k)
        for(int x1=max(1,k-m);x11);x1++)
            for(int x2=max(1,k-m);x21);x2++){
                int t=w[x1][k-x1];
                if(x1!=x2)t+=w[x2][k-x2];
                for(int a=0;a1;a++)
                    for(int b=0;b1;b++)
                        f[k][x1][x2]=max(f[k][x1][x2],f[k-1][x1-a][x2-b]+t);
            }
    
    coutendl;
}

《算法竞赛进阶指南》0x51线性DP 传纸条

标签：线性dp name str pre main 计算 cout end 枚举

原文地址：https://www.cnblogs.com/randy-lo/p/13388361.html

上一篇：数组中去除重复的对象的简单方法

下一篇：线程池在爬虫案例中的应用

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《算法竞赛进阶指南》0x51线性DP 传纸条
文章链接：http://soscw.com/index.php/essay/72408.html

亲，登录后才可以留言！

《算法竞赛进阶指南》0x51线性DP 传纸条

评论

热门文章

推荐文章

最新文章

置顶文章