1875: 蛤瑋的財(cái)寶

Time Limit: 1 Sec??Memory Limit: 128 MB
Submit: 320??Solved: 51

SubmitStatusWeb Board

Description

蛤瑋和他的妹子出海游玩,不小心遭遇了海難,他們醒來(lái)之后發(fā)現(xiàn)自己到了一座金銀島.島主非常好心的告訴他們?cè)趰u的另一邊有船可以送他們回家. 這座島可以看成n*m的矩陣,蛤瑋他們?cè)谖恢?1,1),而船在位置(n,m).蛤瑋發(fā)現(xiàn)金銀島遍地都是金子,每個(gè)格子里有價(jià)值a[i,j]的金子,他和妹子打算在回去的路上帶一些走.如果他們路過(guò)了位置(i,j),就可以假裝系鞋帶撿走地上的金子.為了不引起懷疑,他們?cè)谧叩臅r(shí)候只能往接近碼頭的方向走,即如果蛤瑋現(xiàn)在在(i,j),他只能移動(dòng)到(i+1,j)或者(i,j+1).為了能拿走更多的金子,蛤瑋和妹子決定裝作互相不認(rèn)識(shí),這樣他們就可以分開(kāi)走,從而拿到更多的金子. 蛤瑋和他妹子想知道他們最多能拿走多少金子. 注意如果蛤瑋和他妹子經(jīng)過(guò)了相同的地方,只能得到一次金子,因?yàn)榈厣系膿焱昃蜎](méi)有了.

Input

T(1<=T<=10),表示數(shù)據(jù)組數(shù). 每組數(shù)據(jù)第一行n,m(1<=n,m<=100),接下來(lái)n行,每行m個(gè)數(shù),第i行第j列的值a[i,j](1<=a[i,j]<=1000)表示位置(i,j)的金子的價(jià)值.

Output

每組數(shù)據(jù)輸出一行,蛤瑋和他妹子能拿到的金子總價(jià)的最大值.

Sample Input

12 22 11 2

Sample Output

6

AC代碼：

由于只能往下往右走,所以?xún)蓷l路徑的長(zhǎng)度是一樣的,用dp[k][i][j]表示兩個(gè)人都走了k步,第一個(gè)人在第i行,第二個(gè)人在第j行所能得到的最大值,兩個(gè)人分別往下或往右走一步,有四種轉(zhuǎn)移,如果走到了相同點(diǎn)則權(quán)值只加一個(gè) #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[210][110][110],map[110][110]; int main() {int K,N,M;int i,j,k;int t,l;while(cin>>K)while(K--){cin>>N>>M;for(i=1;i<=N;i++)for(j=1;j<=M;j++)cin>>map[i][j];memset(dp,0,sizeof(dp));dp[2][1][1]=map[1][1];for(k=3;k<N+M;k++){for(i=1;i<=N;i++){for(j=1;j<=N;j++){t=k-i;l=k-j;if(t<1||l<1)break;if(t>M||l>M)continue;dp[k][i][j]=max(max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]),max(dp[k-1][i][j-1],dp[k-1][i][j]))+map[i][t]+map[j][l];if(i==j&&t==l)dp[k][i][j]-=map[i][t];}}}dp[N+M][N][N]=max(max(dp[N+M-1][N-1][N],dp[N+M-1][N-1][N-1]),max(dp[N+M-1][N][N-1],dp[N+M-1][N][N]));cout<<dp[N+M][N][N]+map[N][M]<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的蛤玮的财宝的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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