傳紙條（一）

時(shí)間限制：2000 ms ?|? 內(nèi)存限制：65535 KB 難度：5 描述

小淵和小軒是好朋友也是同班同學(xué)，他們?cè)谝黄鹂傆姓劜煌甑脑掝}。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè)m行n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無(wú)法直接交談了。幸運(yùn)的是，他們可以通過(guò)傳紙條來(lái)進(jìn)行交流。紙條要經(jīng)由許多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。

在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次，也就是說(shuō)如果此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在小軒遞給小淵的時(shí)候就不會(huì)再幫忙。反之亦然。

還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒(méi)有定義，輸入時(shí)用0表示），可以用一個(gè)0-1000的自然數(shù)來(lái)表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來(lái)幫忙傳紙條，即找到來(lái)回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度之和最大?，F(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑。

輸入

第一行輸入N(0<N<100)表示待測(cè)數(shù)據(jù)組數(shù)。
每組測(cè)試數(shù)據(jù)輸入的第一行有2個(gè)用空格隔開(kāi)的整數(shù)m和n，表示班里有m行n列（2<=m,n<=50）。
接下來(lái)的m行是一個(gè)m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學(xué)生的好心程度（不大于1000）。每行的n個(gè)整數(shù)之間用空格隔開(kāi)。

輸出

每組測(cè)試數(shù)據(jù)輸出共一行，包含一個(gè)整數(shù)，表示來(lái)回兩條路上參與傳遞紙條的學(xué)生的好心程度之和的最大值。

樣例輸入

1 3 3 0 3 9 2 8 5 5 7 0

??????? ??????? 這道題剛開(kāi)始的時(shí)候就想到用動(dòng)態(tài)規(guī)劃的方法來(lái)做，以為只是兩次動(dòng)態(tài)規(guī)劃，第二次動(dòng)態(tài)規(guī)劃排除掉第一次走過(guò)的點(diǎn)而已。

????????? 但實(shí)現(xiàn)了單條道路的最大好感度和的計(jì)算之后，卻發(fā)現(xiàn)遠(yuǎn)遠(yuǎn)沒(méi)這么簡(jiǎn)單，兩條道路如何不交叉是一個(gè)問(wèn)題。

??????????? 發(fā)現(xiàn)可以用四維數(shù)組來(lái)動(dòng)態(tài)規(guī)劃解決這道題。

????????? 設(shè)f[i][j][k][l]為從 (0, 0) 位置由兩條不交叉的線路走到 (i, j)，(k, l) 位置時(shí)的最大好感度和，則它的上一步可能有四種情況：

???? ? ?? 第一個(gè)點(diǎn)由上走來(lái)，第二個(gè)點(diǎn)也由上走來(lái)，此時(shí)的好感度和為f[i - 1][j][k - 1][l] + a[i][j] + a[k][l]
??? ? ??? 第一個(gè)點(diǎn)由上走來(lái)，第二個(gè)點(diǎn)則由左走來(lái)，此時(shí)的好感度和為f[i - 1][j][k][l - 1] + a[i][j] + a[k][l]，但此時(shí)應(yīng)考慮第一個(gè)點(diǎn)的上方的點(diǎn)是否會(huì)與第二個(gè)點(diǎn)的左方的點(diǎn)重合，如果重合則不可取
????????? 第一個(gè)點(diǎn)由左走來(lái)，第二個(gè)點(diǎn)則由上走來(lái)，此時(shí)的好感度和為f[i][j - 1][k - 1][l] + a[i][j] + a[k][l]，但此時(shí)應(yīng)考慮第一個(gè)點(diǎn)的左方的點(diǎn)是否會(huì)與第二個(gè)點(diǎn)的上方的點(diǎn)重合，如果重合則不可取
????????? 第一個(gè)點(diǎn)由左走來(lái)，第二個(gè)點(diǎn)也由左走來(lái)，此時(shí)的好感度和為f[i][j - 1][k][l - 1] + a[i][j] + a[k][l]
取四種情況中的最大者即可。

????????? 仔細(xì)審題發(fā)現(xiàn)還可以優(yōu)化掉一維，因?yàn)榈谝粡埣垪l走了k步時(shí)，第二張紙條也必然走了k步，因此我們只需枚舉紙條走了多少步和他的橫坐標(biāo)即可知道縱坐標(biāo)，dp[k][x1][x2]表示走到第k步，第一張紙條的位置x1，y1=k-x1+1;第二張紙條的位置x2，y2=k-x2+1;

?????????? 狀態(tài)轉(zhuǎn)移方程：dp[k][x1][x2] = MAX(dp[k-1][x1][x2], dp[k-1][x1][x2+1], dp[k-1][x1+1][x2], dp[k-1][x1+1][x2+1]) + Map[x1][y1] +? Map[x2][y2];

?????????? 第一種寫(xiě)法：

#include <stdio.h> int n,m; int min(int a,int b){return a<b?a:b;} int max(int a,int b){return a>b?a:b;}int a[51][51]; int f[102][51][51];int main(){int t;scanf("%d", &t);while(t--){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)scanf("%d",&a[i][j]);for (int i=1;i<m+n;i++){for (int x1=1;x1<=min(i,n);x1++){int y1=i-x1+1;if(y1>m) continue;for (int x2=x1+1;x2<=min(i,n);x2++){int y2=i-x2+1;int temp=0;temp=max(f[i-1][x1][x2],f[i-1][x1-1][x2-1]);temp=max(temp,f[i-1][x1-1][x2]);temp=max(temp,f[i-1][x1][x2-1]);f[i][x1][x2]=temp+a[x1][y1]+a[x2][y2];}}}int ans = 0;if(ans < f[m+n-2][n-1][n]) ans = f[m+n-2][n-1][n];if(ans < f[m+n-2][n][n-1]) ans = f[m+n-2][n][n-1];printf("%d\n",ans);}return 0; }

????????? 第二種寫(xiě)法（滾動(dòng)數(shù)組進(jìn)一步優(yōu)化空間）：

#include <iostream> #include <cstdio> #include <cstring>using namespace std;#define MAX(a, b) ((a) > (b) ? (a) : (b)) #define MAXN 51int matrix[MAXN][MAXN]; int dp[2][MAXN][MAXN]; ///滾動(dòng)數(shù)組int MaxSum(int m, int n) {memset(dp, 0, sizeof(dp));int x1, y1, k, x2, y2; ///第一個(gè)紙條在(x1,y1)位置， 第二個(gè)紙條在(x2,y2)位置，紙條傳遞到第k個(gè)位置for (k = m+n-3; k > 0; k--){for (x1 = 0, y1 = k; x1 < m-1; x1++, y1--){if (y1 >= n) ///有人（可傳遞）才計(jì)算{continue;}for (x2 = x1+1, y2 = y1-1; x2 < m; x2++, y2--){dp[k%2][x1][x2] = matrix[x1][y1] + matrix[x2][y2];int r = (k+1) % 2;dp[k%2][x1][x2] +=MAX(MAX(dp[r][x1][x2], dp[r][x1][x2+1]), MAX(dp[r][x1+1][x2], dp[r][x1+1][x2+1]));///到1、2兩個(gè)紙條分別有兩種情況，共有2*2種}}}return dp[1][0][1]; }int main(void) {int ncases;scanf("%d", &ncases);while (ncases-- != 0){int m, n;scanf("%d%d", &m, &n);memset(matrix, 0, sizeof(matrix));int i, j;for (i = 0; i < m; i++){for (j = 0; j < n; j++){scanf("%d", &matrix[i][j]);}}printf("%d\n", MaxSum(m, n));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的nyoj 61 传纸条（一） （双线动归）nyoj 探寻宝藏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。