思路：动态规划

首先，观察本题的跳跃方式，有一个共性特点：只会向右跳跃

对于每个位置，我们需要考虑四种跳跃方式：先向右走一步，再向上或向下走两步，或者先向右走两步，再向上或向下走一步。

我们可以定义长度为4的方向数组，来表示这四种跳跃方式

定义$f[i][j]$表示到达$(i,j)$点的最大硬币数量，那么我们可以枚举$(i,j)$是由上述哪一种方式跳跃得到的

状态转移方程为：$f[i][j]=max(f[i][j],f[a][b]+w[i][j])$

更新的时候需要按照列，也就是$j$来更新，这一点需要注意。

代码

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,w[N][N];
long long f[N][N];
const long long mod = 1e9 + 7;
int dx[4]={1,-1,2,-2},dy[4]={2,2,1,1};   //四个方向
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>w[i][j];
        }
    }
    memset(f,-0x3f,sizeof f);
    f[1][1]=w[1][1];
    for(int i=2;i<=n;i++)  //第i列
    {
        for(int j=1;j<=n;j++){
            for(int k=0;k<4;k++){
                int x=j-dx[k],y=i-dy[k];
                if(x<1||x>n||y<1||y>n)continue;
                f[j][i]=max(f[j][i],f[x][y]+w[j][i]);
            }
        }
    }
    long long res=0;
    for(int i=1;i<=n;i++)
        res=max(res,f[i][n]);
    cout<<res<<endl;
  return 0;

}

Java

import java.util.*;
import java.io.*;
class ac extends PrintWriter {
    BufferedReader br;
    StringTokenizer st;
    ac() {this(System.in, System.out);}
    ac(InputStream i, OutputStream o) {
        super(o);
        br = new BufferedReader(new InputStreamReader(i));
    }

    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int nextInt() {return Integer.parseInt(next());}
    long nextLong(){return Long.parseLong(next());}

}
public class Main{
    public static void main(String[] args) {
        ac in=new ac();
        new B(in);
        in.flush();
    }
}
class B{
    int mp[][];
    long dp[][];
    int addy[]=new int[]{2,2,1,1};
    int addx[]=new int[]{1,-1,2,-2};
    B(ac in){
        int n=in.nextInt();
        mp=new int[n][n];
        dp=new long[n][n];
        for(long []p:dp)Arrays.fill(p,Long.MIN_VALUE/2);
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)mp[i][j]=in.nextInt();
        dp[0][0]=mp[0][0];

        for(int i=1;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<4;k++){
                    int x=j-addx[k],y=i-addy[k];
                    if(x<0||x>n-1||y<0||y>n-1)continue;
                    dp[j][i]=Math.max(dp[j][i],dp[x][y]+mp[j][i]);
                }
            }
        }
        
        long res=0L;
        for(int i=0;i<n;i++){
            res=Math.max(res,dp[i][n-1]);
        }
        in.println(res);
    }
}

python

n = int(input())
w = [[0]*(n+1) for _ in range(n+1)]
f = [[float('-inf')]*(n+1) for _ in range(n+1)]
dx = [1, -1, 2, -2]
dy = [2, 2, 1, 1]
mod = 10**9 + 7

for i in range(1, n+1):
    w[i] = [0]+list(map(int, input().split()))

f[1][1] = w[1][1]
for i in range(2, n+1):
    for j in range(1, n+1):
        for k in range(4):
            x, y = j - dx[k], i - dy[k]
            if x < 1 or x > n or y < 1 or y > n:
                continue
            f[j][i] = max(f[j][i], f[x][y] + w[j][i])

res = 0
for i in range(1, n+1):
    res = max(res, f[i][n])

print(res)

题目描述

教练我也想学这个！在一个n*n的正方形训练场上中下标从1-n，每个位置都有一枚硬币，小明从起点出发，跳跃可以先向右走一步，再向上或向下走两步，或者先向右走两步，再向上或向下走一步。但是小明不能跳出训练场，也不能往回跳，不然会遭到教练的严厉表扬。小明左上位置(1,1)上，他想在完成训练获得更多的硬币买快乐水。身为教练的你要帮他吗？

输入描述

第一行输入一个整数n$(3\le n\le 1000)$表示操场大小。接下来n行，每行输入n个整数表示每个位置的权值 $(1\le a_{ij}\le 10^9)$

输出描述

输出一个整数表示答案。

样例

输入

3
1 1 4
5 1 4
1 9 19

输出

14

Limitation

1s, 1024KiB for each test case.