题解：SP3923 BYTESM2 - Philosophers Stone

__CrossBow_EXE__ · 2025-08-05 19:02:09 · 题解

题意

一个 n \times m 点矩形 a，给出每个点的权值。CEXE 从第一行出发往下走，每次可以从 a_{i,j} 到达 a_{i+1,j-1},a_{i+1,j},a_{i+1,j+1}。到达一个点可以取走一个点的权值，求最大权值和。

分析

神秘动态规划。

定义 dp_{i,j} 为到达第 i 行第 j 列的最大权值和，发现由左上、上方、右上可以过来，不难写出转移方程：dp_{i,j}=\max\{dp_{i-1,j-1},dp_{i-1,j},dp_{i-1,j+1} \}，其中 2 \le i \le n,1 \le j \le m。初始化为 dp_{1,i}=a_{1,i}，其中 1 \le i \le m。注意多测。

时间复杂度 O(Tnm)。

代码

#include<bits/stdc++.h>
using namespace std;
#define up(_name_,_leftbound_,_rightbound_) for(auto _name_=(_leftbound_);(_name_)<=(_rightbound_);++(_name_))
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int a[105][105];
int dp[105][105];
void solve(int cases){
    n=read(),m=read();
    up(i,1,n){
        up(j,1,m){
            a[i][j]=read();
        }
    }
    memset(dp,0,sizeof(dp));
    up(i,1,m) dp[1][i]=a[1][i];
    up(i,2,n){
        up(j,1,m){
            dp[i][j]=max({dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]})+a[i][j];
        }
    }
    int maxn=-1;
    up(i,1,m){
        maxn=max(maxn,dp[n][i]);
    }
    cout<<maxn<<endl;
    return;
}
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    T=read();
    up(i,1,T) solve(i);
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/8/5 18:37:51
PROBLEM:SP3923
CODE BY __CrossBow_EXE__ Luogu uid967841
CEXE好闪，拜谢CEXE。
*/

已 AC。