常用的网站推广的方式方法,企业logo设计创意,大连公司注册,有做ppt的兼职网站吗传送门 走两次 dp[x1][y1][x2][y2]表示两条路分别到两个点的坐标后的最大值 为了防止走重#xff0c;dp[x1][y1][x1][y1]赋值为无穷小 时间复杂度O#xff08;n^4#xff09;
代码
#includecstdio
#includecstring
#includealgorithm
#includedp[x1][y1][x1][y1]赋值为无穷小 时间复杂度On^4
代码
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N60;
int a[N][N],dp[N][N][N][N];
int m,n;
int max4(int a,int b,int c,int d){return max(a,max(b,max(c,d)));
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){for(int j1;jm;j) scanf(%d,a[i][j]);}for(int x11;x1n;x1){for(int y11;y1m;y1){for(int x21;x2n;x2){for(int y21;y2m;y2){if(x1x2y1y2(x1!n||y1!m)) dp[x1][y1][x2][y2]-2e9;else{dp[x1][y1][x2][y2]max4(dp[x1-1][y1][x2-1][y2]a[x1][y1]a[x2][y2],dp[x1-1][y1][x2][y2-1]a[x1][y1]a[x2][y2],dp[x1][y1-1][x2-1][y2]a[x1][y1]a[x2][y2],dp[x1][y1-1][x2][y2-1]a[x1][y1]a[x2][y2]);}}}}}printf(%d,dp[n][m][n][m]);
}
/*
3 3
0 3 9
2 8 5
5 7 0
*/优化
用k表示走的步数 dp[k][y1][y2]表示两条路径走到的点纵坐标分别为y1y2 那么横坐标分别为k-y12,k-y22 注意横坐标也必须在1到m的范围内
代码
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N60;
int a[N][N],dp[2*N][N][N];
int m,n;
int max4(int a,int b,int c,int d){return max(a,max(b,max(c,d)));
}
int main(){scanf(%d%d,n,m);for(int i1;in;i){for(int j1;jm;j) scanf(%d,a[i][j]);}for(int k1;knm-2;k){for(int y11;y1m;y1){if(k-y121||k-y12n) continue;for(int y21;y2m;y2){if(k-y221||k-y22n){continue;}if(y1y2(y1!m||k-y12!n)) dp[k][y1][y2]-2e9;else dp[k][y1][y2]max4(dp[k-1][y1][y2],dp[k-1][y1-1][y2-1],dp[k-1][y1-1][y2],dp[k-1][y1][y2-1])a[k-y12][y1]a[k-y22][y2];}}}printf(%d,dp[nm-2][m][m]);
}
/*
3 3
0 9 9
6 1 8
2 3 0
*/心得
本题之前做过但仍然不耽误忘 主要是没有想到赋值成无穷小的方法以去除决策 学废了
