dp Mzx0821月赛系列之情书(1084)

<p>    一次班上做活动，班上同学被安排坐成m行n列的矩阵，Mzx0821坐在坐标（x1,y1）的位置，Zzx坐在坐标（x2,y2）的位置。活动过程中，Mzx0821写了一张纸条想给Zzx，但是Mzx0821又不想班上其他人看到他写的内容，于是Mzx0821给班上每个人定义了一个保密程度值（就是这个人不偷看纸条内容的可能），每个人传递纸条只能给前后左右的人。</p> <p>    Mzx0821还考虑到万一Zzx给Mzx0821回纸条怎么办呢，为了保密，Mzx0821希望每个人最多传递一次纸条，就是说一个人在Mzx0821传给Zzx的时候帮了忙，就不能再帮Zzx传给Mzx0821，反之亦然。</p> <p>    Mzx0821希望找到这样两条路，使得来回两条路上的保密程度值的和最大，为了尽快传到，这两条路必须是Mzx0821到Zzx的之间的最短路。</p> <p>    Mzx0821智商实在捉急，于是向机智的学弟学妹们求助，你能帮助他找到正确的路线吗？</p> 一道dp题目 四维数组记录 i+j=k+l 及三成循环可以遍历所有情况 题目链接<a target=_blank href="http://acm.swust.edu.cn/problem/1084/">点击打开链接</a> #include<iostream> #include<cstdio> #include<cstring> #include<map> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #define LL long long using namespace std; int max(int x, int y, int k, int l) { int m = x > y ? x : y; m = m > k ? m : k; m = m > l ? m : l; return m; } int dp[55][55][55][55] = { 0 }; //i + j = k + l; int main() { int n, m, map[55][55], i, j, k, l; while( scanf("%d%d", &n, &m)!=EOF) { for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { scanf("%d", &map[i][j]); } } if(m<2|| n<2) { printf("0\r\n"); continue; } for(i = 1;i <= n;i++) { for (j = 1; j <= m; j++) { for (k = i+1; k <= n; k++) //i+1保证他们不会有交集 { l = i + j - k; if (l>m||l<=0) { continue; } dp[i][j][k][l] = max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])+map[i][j]+map[k][l]; } } } printf("%d\r\n",dp[n-1][m][n][m-1]); } return 0; }