双线程DP
求从N*M矩形的左上角到右下角两条路径的最大值
下面的代码中:
a[i][j]代表:任意一点的路程
b[i][j][k][l]代表:一点在i,j处,另一点在k,l处时所能取得的最大值
#include <cstdio> #include <iostream> #include <cmath> using namespace std; int a[55][55]; int b[55][55][55][55]; int main () { int n,m; cin >> n >> m; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cin >> a[i][j]; } } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) for (int k=1;k<=n;k++) for (int l=1;l<=m;l++) { if(i!=k||j!=l||(i==n&&j==m&&k==n&&l==m)) { b[i][j][k][l]=max(b[i][j][k][l],b[i-1][j][k-1][l]); b[i][j][k][l]=max(b[i][j][k][l],b[i-1][j][k][l-1]); b[i][j][k][l]=max(b[i][j][k][l],b[i][j-1][k-1][l]); b[i][j][k][l]=max(b[i][j][k][l],b[i][j-1][k][l-1]); b[i][j][k][l]+=a[i][j]+a[k][l]; } } cout << b[n][m][n][m] << endl; return 0; }