DFS的高维【四维DFS】洛谷p1006传纸条

题目链接洛谷P1006传纸条 本题的原理与洛谷P1004方格取数相同。在不考虑优化的情况下可以直接使用四维dp，因为数据较弱，最多也只有505050*50=6250000的复杂度，不用担心爆空间或超时。

还请各位用三维二维数组的大佬不要鄙视本蒟蒻~

题解：

就是用f[i][j][k][l]，其中[i][j]存小渊来信的路径，[k][l]则存小轩的。这信一来一回啊，可以等价于信从小渊这里向右下方传了两次，（这样是不是基本上算p1004_方格取数的大致过程了，哈哈哈哈哈哈）。 然后呢，再看信件走的路径：四种情况 1.A信封下，B信封右 2.A信封下，B信封下 3.A信封右，B信封下 4.A信封右，B信封右 综上，我们可以得到dp方程： 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]; **

注意几点点：

** 1…在dp的过程中，不要忘记特判一下这两条路径是不能重复的 2…最后输出的时候并不是f[m][n][m][n],因为dp到最后并不是小轩的点，而是到他上方和左方就结束了！所以应该是f[m][n-1][m-1][n] 3…烂大街的问题：数组一定要够大，否则就…

AC代码：

#include<iostream> #include<cstring>//memset需要用 using namespace std; int m, n; int f[51][51][51][51], a[51][51];//范围到50，多开一个 int main(){ cin >> m >> n; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; j++){ cin >> a[i][j];//读入二维数组 } } f[1][1][1][1] = 0; //删了这行不影响结果 for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ for(int k=1; k<=m; k++){ for(int l=1; l<=n; l++){ if(i != k && j != l) //原则是两条路径不能重复，才能进行dp f[i][j][k][l] = max(f[i-1][j][k-1][l], max(f[i-1][j][k][l-1], max(f[i][j-1][k-1][l], f[i][j-1][k][l-1]))) + a[i][j] + a[k][l];//动态规划方程 } } } } cout << f[m][n-1][m-1][n] << endl;//实际走不到最后一个点，最后一步分别定在上/左方向 return 0; } /* 3 3 0 3 9 2 8 5 5 7 0 34 */