描述:
小淵和小軒是好朋友也是同班同學,他們在一起總有談不完的話題。一次素質拓展活動中,班上同學安排做成一個m行n列的矩陣,而小淵和小軒被安排在矩陣對角線的兩端,是以,他們就無法直接交談了。幸運的是,他們可以通過傳紙條來進行交流。紙條要經由許多同學傳到對方手裡,小淵坐在矩陣的左上角,坐标(1,1),小軒坐在矩陣的右下角,坐标(m,n)。從小淵傳到小軒的紙條隻可以向下或者向右傳遞,從小軒傳給小淵的紙條隻可以向上或者向左傳遞。
在活動進行中,小淵希望給小軒傳遞一張紙條,同時希望小軒給他回複。班裡每個同學都可以幫他們傳遞,但隻會幫他們一次,也就是說如果此人在小淵遞給小軒紙條的時候幫忙,那麼在小軒遞給小淵的時候就不會再幫忙。反之亦然。
還有一件事情需要注意,全班每個同學願意幫忙的好感度有高有低(注意:小淵和小軒的好心程度沒有定義,輸入時用0表示),可以用一個0-100的自然數來表示,數越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條,即找到來回兩條傳遞路徑,使得這兩條路徑上同學的好心程度隻和最大。現在,請你幫助小淵和小軒找到這樣的兩條路徑。
輸入格式:
輸入第一行有2個用空格隔開的整數m和n,表示班裡有m行n列(1<=m,n<=50)。
接下來的m行是一個m*n的矩陣,矩陣中第i行j列的整數表示坐在第i行j列的學生的好心程度。每行的n個整數之間用空格隔開。
輸出格式:
輸出共一行,包含一個整數,表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。
樣例輸入:
3 3
0 3 9
2 8 5
5 7 0
樣例輸出:
34
我們轉化一下思想,題目中說由左上方到右下方來回,我們可以看作是從左上方找兩條不相交的路徑到右下方。這裡我們可以好比是兩個紙條同時從左上方向右下方傳,隻要保證在同一時刻兩個紙條不在同一個人手裡,那麼我們就能保證兩個字條的路徑不相交.
确定算法: DP(動态規劃)
狀态:目前時刻的兩個字條的坐标。
狀态轉移方程式 :
dp[i][j][x][y]=
max{ dp[i-1][j][x-1][y],dp[i-1][j][x][y-1],dp[i][j-1][x-1][y],dp[i][j-1][x][y-1] }+num[i][j]+num[x][y]
為了保證兩個字條是同步傳遞的,是以方程式要加一個限定條件 ( i + j = x + y )☆
#include<stdio.h>
int dp[51][51][51][51];
int num[51][51];
int max(int a,int b,int c,int d)
{
if(a>b&&a>c&&a>d)return a;
if(b>a&&b>c&&b>d)return b;
if(c>b&&c>a&&c>d)return c;
return d;
}
int main()
{
int n,m;
int i,j,x;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&num[i][j]);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
for(x=1;x<=n;x++)
{
int y=i+j-x;
if(i>x&&y>=0)
{
dp[i][j][x][y]=max(dp[i-1][j][x-1][y],dp[i-1][j][x][y-1],dp[i][j-1][x-1][y],dp[i][j-1][x][y-1])++num[i][j]+num[x][y];
}
}
}
}
printf("%d\n",dp[n][m-1][n-1][m]);
return 0;
}
代碼優為三維:
#include<cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int mpt[52][52],dp[52][52][52],n,m;
int max(int a,int b,int c,int d)
{
int e,f;
e=(a>b)? a:b;
f=(c>d)? c:d;
return (e>f)? e:f;
}
int main()
{
int i,j,x;
cin>>n>>m;
for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>mpt[i][j];
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
for(x=1;x<i;x++){
dp[i][j][x]=max(dp[i-1][j][x-1],dp[i-1][j][x],dp[i][j-1][x-1],dp[i][j-1][x])+mpt[i][j]+mpt[x][i+j-x];
}
}
}
cout<<dp[n][m-1][n-1]<<endl;
return 0;
}