本文主要是介绍洛谷 P1006 传纸条，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
洛谷 P1006 传纸条
- 1.问题分析
- 2.具体代码
- 3.总结
题目链接
（第一次写没想出来，毕竟是第一次遇见四维dp）
1.问题分析
本质上就是P1004问题，代码都不用改
利用y总的dp问题分析方法：
转换成小渊向小轩传两次纸条。
集合f(a,b,c,d)的含义为：两次分别走到(a,b),(c,d)两点。
性质为max。
集合的划分：
1.可以划分成四个部分1.f(a-1,b,c-1,d)，2.f(a-1,b,c,d-1)，3.f(a,b-1,c-1,d)，4.f(a,b-1,c,d-1)。
2.（具体问题具体分析）需要注意的是当(a,b),(c,d)两点两点相同时根据题意需要减去一个map[a][b]。（因为求的是max，所以答案不受影响）
2.具体代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 51;
int map[N][N];
int dp[N][N][N][N];
int n,m,x;
int main()
{cin>>m>>n;for(int a=1;a<=m;a++)for(int b=1;b<=n;b++){cin>>x;map[a][b]=x;}for(int a=1;a<=m;a++)for(int b=1;b<=n;b++)for(int c=1;c<=m;c++)for(int d=1;d<=n;d++){dp[a][b][c][d]=max(max(dp[a-1][b][c-1][d],dp[a-1][b][c][d-1]),max(dp[a][b-1][c-1][d],dp[a][b-1][c][d-1]))+map[a][b]+map[c][d];if(a==c&&b==d) dp[a][b][c][d]-=map[a][b];}cout<<dp[m][n][m][n]<<endl;return 0;
}3.总结
太菜了，要增加刷题量。
这篇关于洛谷 P1006 传纸条的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
