$\huge\tt{Hello\ \color{red}{M}\color{#9D3DCF}{X}\color{#3498DB}{O}\color{52c41a}{J}}!$
这是 MXOJ 的第一个帖子，也是目前唯一一个帖子，其他的都被删除了。
这是楼主在 MXOJ 中闲逛时发现这道题可以发讨论，于是就有了这个帖子。
楼主是洛谷的 Xlon_Rainfi。
这里相当于一个小讨论区，你可以在本贴下回复以讨论
83 条评论
-
zezechoicec LV 2 @ 2025-9-10 21:36:31🟠
-
@ 2025-9-10 21:36:01
🥳
-
@ 2025-9-9 22:44:21
https://oier.team/problems/J3E
https://www.luogu.com.cn/problem/P10997
n^3 暴力，but 没过样例（有思路，感觉是对的）
Analysis
本解中，交叉点表示的是这个格子左上角的那个点。规定最右侧的一排交叉点为 ，最下面一排用 表示。
红橙与黄绿分割线和红黄与橙绿分割线会形成一个抽象的
X形。可设 表示当前在第 行，红橙/黄绿分割线在第 列，红黄/橙绿分割线在第 列的最大总和。同时设 表示第 i 行的前缀和，那么有转移方程：
$$dp(i,l,r) = \begin{cases} \max(dp(i,l-1,r),dp(i,l,r+1),dp(i-1,l,r) + 2s_{i,m} - s_{i,r-1} + 2s_{i, l-1}) & l\le r\\ \max(dp(i,l-1,r),dp(i,l,r+1),dp(i-1,l,r) + 2s_{i,m} + 2s_{i,r-1} - s_{i, l-1}) & l>r \end{cases} $$
Problem
滚动后时空应该可以过 。but，样例输出了
66。#include <bits/stdc++.h> // 55 pts using namespace std; using ll = long long; int n, m; ll s[505][505], dp[2][505][505]; int main(){ cin.tie(0) -> sync_with_stdio(0); cin >> n >> m; for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ cin >> s[i][j]; s[i][j] += s[i][j-1]; } } memset(dp, -0x7f, sizeof dp); for(int l=1; l<=m+1; ++l){ for(int r=1; r<=1+m; ++r){ dp[0][l][r] = 0; } } for(int i=1; i<=n; ++i){ for(int l=1; l<=m+1; ++l){ for(int r=m+1; r>=l; --r){ dp[i&1][l][r] = max({dp[i&1][l-1][r], dp[i&1][l][r+1], dp[(i-1) & 1][l][r] + 2 * s[i][m] - s[i][r-1] + 2 * s[i][l-1]}); //if(i == 2)cout << dp[i][l-1][r] << ' ' << dp[i][l][r+1] << ' ' << dp[i-1][l][r] + 2 * s[i][m] - s[i][r-1] + 2 * s[i][l-1] << '\n'; } for(int r=l-1; r; --r){ dp[i&1][l][r] = max({dp[i&1][l-1][r], dp[i&1][l][r+1], dp[(i-1) & 1][l][r] + 2 * s[i][m] + 2 * s[i][r-1] - s[i][l-1]}); //if(i == 2)cout << dp[i][l-1][r] << ' ' << dp[i][l][r+1] << ' ' << dp[i-1][l][r] + 2 * s[i][m] + 2 * s[i][r-1] - s[i][l-1] << '\n'; } } } ll ans = -1e15; for(int i = /*1*/ n; i<=n; ++i){ for(int l=1; l<=m+1; ++l){ for(int r=1; r<=m+1; ++r){ // cout << dp[i][l][r] << ' '; ans = max(ans, dp[n&1][l][r]); } // cout << '\n'; } // cout << '\n'; } cout << ans << '\n'; return 0; }我想给他完整的一生。🚾 2-
@ 2025-9-9 22:46:20
应该就我一个来发求调的（
-
-
@ 2025-8-19 20:04:47？梦熊OJ证书过期了
-
@ 2025-8-10 11:53:43 -
@ 2025-8-3 11:14:03hp
-
@ 2025-7-29 9:30:05fc
-
@ 2025-7-28 8:59:57
-
@ 2025-7-24 18:33:09
大家都来洛谷吗？
-
@ 2025-7-23 14:28:38
yeah?
-
@ 2025-7-6 21:25:151
-
@ 2025-7-2 22:42:01
喵~
-
@ 2025-6-25 20:22:26
说句闲话：研究珂学的最好方法是
🇯🇵 3 -
@ 2025-6-23 20:47:10
此贴≈洛谷灌水区
-
@ 2025-6-21 17:37:11
qp
-
@ 2025-6-17 19:50:29666
🦍 3 -
@ 2025-6-13 21:00:05
啊？
🏛️ 2 -
@ 2025-6-11 22:18:38
qp
-
@ 2025-6-10 21:01:28
qp
-
@ 2025-6-4 20:06:51qp 考古
-
@ 2025-6-4 7:08:10qp
-
@ 2025-6-1 17:30:45
回望历史吧，孩子，感受洛阳铲的力量,并在力量的熏陶下“……”…… 好像我也说不出来什么了（一介洛谷难民）
-
@ 2025-6-1 17:17:07
神前刘明
-
@ 2025-5-31 21:34:34
hp
-
@ 2025-5-30 17:37:11
-
@ 2025-5-28 20:19:22
qp
but为啥其他的都被删除了
-
@ 2025-5-18 10:27:48qp
-
@ 2025-5-5 13:58:55
qp
-
@ 2025-5-4 15:09:58厉害
-
@ 2025-5-2 17:32:12
666
-
@ 2025-4-30 19:04:45
66666
-
@ 2025-4-28 20:27:33
qp
-
@ 2025-4-28 12:48:33
qp
-
@ 2025-4-27 20:45:21
qp
-
@ 2025-4-26 21:35:05
qp
-
@ 2025-4-21 17:10:55
666
😇 5😄 5🙃 4😉 4 -
@ 2025-4-20 19:10:17论在哪里才能看到赛时答疑帖
-
@ 2025-4-12 15:49:01
111
-
@ 2025-4-10 17:03:24
怎么只剩这一个帖子了喵～
😇 5-
@ 2025-4-10 17:03:47
尝试回复
-
-
@ 2025-3-30 22:23:30qp
-
@ 2025-3-29 12:48:14
qp
-
@ 2025-3-27 23:00:57
笑了
-
@ 2025-3-23 17:53:32
MXOJ是Hydro吧
-
@ 2025-4-11 19:59:42
确实是，可以看admin.oier.team
-
-
@ 2025-3-15 22:56:04
前排
😃 1 -
@ 2025-3-8 10:53:33
%%%
-
@ 2025-3-3 20:57:55
后排
-
@ 2025-3-2 16:25:19
试图回复
-
@ 2025-3-1 20:26:04后排落座，不要吵闹。
轻轻一踢，踢爆前排。
往前一座，我即前排。
-
@ 2025-3-1 15:08:18
有人么qmq？？
-
@ 2025-2-28 20:07:26
q(?)p
