题解 | #あなたの蛙は旅立っています#

写一篇不需要转化原图的题解。

直接根据数字三角形的思路，原图的结构模拟这一过程 dp 即可，注意我们 dp 的过程可以分为下面三段：

上图是我自己画的。

第一部分是一个裸的数字三角形，注意这里每一行可以通过上一行和上两行转移过来即可。图中的数字表示行号。

第二部分是一个 $n-1,nn-1,n$ 交替的结构，第三部分是一个倒着的数字三角形，根据图即可观察得出转移方程：

第一部分：$a[i][j]\leftarrow \max (a[i-2][j-1],\max (a[i-1][j-1],a[i-1][j]))a[i][j]\; \backslash leftarrow\; \backslash max(a[i\; -\; 2][j\; -\; 1],\; \backslash max(a[i\; -\; 1][j\; -\; 1],\; a[i\; -\; 1][j]))$

第二部分（$nn$ 段）：$a[i][j]\leftarrow \max (a[i-2][j],\max (a[i-1][j-1],a[i-1][j]))a[i][j]\; \backslash leftarrow\; \backslash max(a[i\; -\; 2][j],\; \backslash max(a[i\; -\; 1][j\; -\; 1],\; a[i\; -\; 1][j]))$

第二部分（$n-1n-1$ 段）：$a[i][j]\leftarrow \max (a[i-2][j],\max (a[i-1][j],a[i-1][j+1]))a[i][j]\; \backslash leftarrow\; \backslash max(a[i\; -\; 2][j],\; \backslash max(a[i\; -\; 1][j],\; a[i\; -\; 1][j\; +\; 1]))$

第三部分：$a[i][j]\leftarrow \max (a[i-2][j+1],\max (a[i-1][j],a[i-1][j+1]))a[i][j]\; \backslash leftarrow\; \backslash max(a[i\; -\; 2][j\; +\; 1],\; \backslash max(a[i\; -\; 1][j],\; a[i\; -\; 1][j\; +\; 1]))$

#include<cstdio>
#include<cstring>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 4e3 + 5;
int a[N][N];
int mx(int x, int y){
    return x > y ? x : y;
}
signed main(){
    int n = init();
    memset(a, -0x3f, sizeof(a));
    a[1][1] = init();
    for (int i = 2; i <= 4 * n - 3; ++i)
        if (i <= n) /* 第 1 ~ n 行：第 i 行 i 个数 */
            for (int j = 1; j <= i; ++j)
                a[i][j] = mx(a[i - 2][j - 1], mx(a[i - 1][j - 1], a[i - 1][j])) + init();
        else if (i <= 3 * n - 1) /* 第 n + 1 ~ 3n - 1 行：
                第 n + 1, n + 3, ..., 3n - 1 行 n - 1 个数
                第 n + 2, n + 4, ..., 3n - 2 行 n 个数 */
            if ((i & 1) xor ((n + 1) & 1))
                /* 奇偶性不同，n 个数*/
                for (int j = 1; j <= n; ++j)
                    a[i][j] = mx(a[i - 2][j], mx(a[i - 1][j - 1], a[i - 1][j])) + init();
            else /* 奇偶性相同，n - 1 个数 */
                for (int j = 1; j < n; ++j)
                    a[i][j] = mx(a[i - 2][j], mx(a[i - 1][j], a[i - 1][j + 1])) + init();
        else
            /* 第 3n ~ 4n - 3 行：分别是 n - 2, n - 3, ..., 1 个数 */
            for (int j = 1; i + j <= 4 * n - 2; ++j)
                a[i][j] = mx(a[i - 2][j + 1], mx(a[i - 1][j], a[i - 1][j + 1])) + init();
    print(a[4 * n - 3][1]), putchar('\n');
}