那23個路口
題面
故事的起源不加贅述，那23個路口，
單刀直入，我直接說題的意思，
蚊子和瘋子在做一件事，就是他們要在茫茫的大街上找一個出發點，然后從出發點開始，經過上下左右23次拐彎，到達一個他們也不知道的地方，
老城的街道排列的十分有規律，于是瘋子和蚊子把老城的街道排布畫在了一張地圖上，地圖上每一個點代表一個地方，而這個地方有一定的憧憬值，瘋子希望可以帶蚊子走過的二十三個路口的憧憬值總和是所有方案中最大的，
現在我們讀入一個矩陣，如果此點為0，則這個點為起點，如果此點為-1，則這個點為障礙點，否則這個數代表憧憬值，注意起點和障礙點是沒有憧憬值的，起點只有開始的時候可以達到，不可以再回來，而障礙點根本就不可以走過，這樣一來，請你選擇合適的路線，使走完23個路口后得到最大的憧憬值，有憧憬值的點可以重復進出，每次可以選擇四個方向，上下左右，起點為第0個路口
輸入格式
第1行兩個整數 n,m （茫茫大街的長和寬）
第2行到第m+1行，每行n個整數\(A_{ij}\)（第I行第j個地點的憧憬值）
輸出格式
一個整數sum （可以得到的最大憧憬值）
樣例
\(\texttt{input\#1}\)
4 4
1 1 1 1
1 1 0 1
1 1 1 1
1 1 1 1
\(\texttt{output\#1}\)
23
資料范圍與提示
于30%的資料，\(n,m \leqslant 50\)
0<n,m<300，每個點的憧憬值可以用longint表示，
題解
dp，f[i][j][k]表示第k步走到(i,j)這個位置的最大憧憬值.則有，
if(map[i][j]<=0) continue;
if(j>1&&map[i][j-1]>=0) f[i][j][k]=max(f[i][j][k],f[i][j-1][k-1]+map[i][j]);
if(j<m&&map[i][j+1]>=0) f[i][j][k]=max(f[i][j][k],f[i][j+1][k-1]+map[i][j]);
if(i>1&&map[i-1][j]>=0) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+map[i][j]);
if(i<n&&map[i-1][j]>=0) f[i][j][k]=max(f[i][j][k],f[i+1][j][k-1]+map[i][j]);
\(Code\)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define max(a,b) a>b?a:b
#define MAXN 301
typedef long long ll;
int n,m;
ll f[MAXN][MAXN][24],map[MAXN][MAXN],ans;
inline void read(ll &T) {
ll x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
int main() {
scanf("%d%d",&m,&n);
memset(f,-0x3f3f3f,sizeof(f));
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
read(map[i][j]);
if(map[i][j]==0) f[i][j][0]=0;
}
}
for(int k=1;k<=23;++k) {
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(map[i][j]<=0) continue;
if(j>1&&map[i][j-1]>=0) f[i][j][k]=max(f[i][j][k],f[i][j-1][k-1]+map[i][j]);
if(j<m&&map[i][j+1]>=0) f[i][j][k]=max(f[i][j][k],f[i][j+1][k-1]+map[i][j]);
if(i>1&&map[i-1][j]>=0) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]+map[i][j]);
if(i<n&&map[i-1][j]>=0) f[i][j][k]=max(f[i][j][k],f[i+1][j][k-1]+map[i][j]);
}
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(ans<f[i][j][23]) ans=f[i][j][23];
}
}
std::cout<<ans<<'\n';
return 0;
}
上接【CSP-S膜你考】不怕噩夢 （模擬）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/93378.html
標籤：C++