暴搜($3^{(n^2)}$ 20pts)

• 从起点开始搜索每个节点，搜到终点以后更新答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010;
int g[N][N];
int a[N][N];
bool st[N][N];
int dx[]={1,-1,0},dy[]={0,0,1}; //可以走的方向
int n,m;
LL ans=-2e9;
void dfs(int x,int y,LL sum)
{
    if(x==n&&y==m) //找到终点
    {
        ans=max(ans,sum);
        return ;
    }
    for(int i=0;i<3;i++) //枚举所有走法
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>m) continue;
        if(st[a][b]) continue;
        st[a][b]=true;
        dfs(a,b,sum+g[a][b]);
        st[a][b]=false;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    st[1][1]=true;
    dfs(1,1,g[1][1]); //从起点开始搜索
    cout<<ans<<endl;
	return 0;
}

动态规划($O(n^2)$ 100pts)

• $f[i][j]$表示走到$(i,j)$这个位置的最大值，然后方向不能确定，因为当前如果往上就不能往下，所以再开一维表示上下，从左边过来可以加到上下里面。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
typedef long long LL;
int n,m;
int w[N][N];
LL f[N][N][2];
/*
f[i][j][0]表示从左边或者是上边过来的最大值
f[i][j][1]表示从左边或者是下边做来的最大值
*/
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    memset(f,0xcf,sizeof f); //初始化
    f[1][0][0]=0; //入口
    for(int j=1;j<=m;j++) //从左往右计算
    {
        for(int i=1;i<=n;i++) //从上往下计算
        {
            f[i][j][0]=max(max(f[i][j-1][0],f[i][j-1][1]),f[i-1][j][0])+w[i][j];
        }
        for(int i=n;i>=1;i--) //从下往上计算
        {
            f[i][j][1]=max(max(f[i][j-1][0],f[i][j-1][1]),f[i+1][j][1])+w[i][j];
        }
    }
    cout<<f[n][m][0];
    return 0;
}