你好，梦熊 OJ！
Hello MXOJ! | MXOJ 讨论区（伪
wuxinlong @ 2024-6-29 9:40:45

$\huge\tt{Hello\ \color{red}{M}\color{#9D3DCF}{X}\color{#3498DB}{O}\color{52c41a}{J}}!$

这是 MXOJ 的第一个帖子，也是目前唯一一个帖子，其他的都被删除了。

这是楼主在 MXOJ 中闲逛时发现这道题可以发讨论，于是就有了这个帖子。

楼主是洛谷的 Xlon_WU。

~~这里相当于一个小讨论区，你可以在本贴下回复以讨论~~

已修改
784 次查看
举报

🎉 104

🤫 57

👻 47

🤠 45

🍭 45

🙊 43

🙃 36

😀 34

🐒 29

😚 28

🐈 28

😍 27

😄 27

6️⃣ 26

😅 25

☺️ 25

😪 25

😉 24

😥 24

😢 23

😆 23

😫 22

💥 22

🫠 22

☠️ 22

😣 21

😦 21

💟 21

💝 21

🦅 21

🐣 21

🙂 21

😨 20

😁 20

😘 20

🤤 20

🥸 20

💔 20

🐯 20

🦓 20

🦆 20

🤭 20

😑 20

😜 20

🥺 19

❤️‍🔥 19

🧡 19

🤮 19

💖 19

🤖 19

😸 19

😹 19

🎋 19

🏈 19

🐗 19

☣️ 19

🦌 18

🪶 18

🐅 18

🤨 18

🌏 18

🇮🇳 18

🏧 18

🥜 18

🥢 18

🦚 17

☘️ 17

🐶 17

🦊 17

😇 17

🍈 17

🤢 17

🍇 16

🍉 16

🍍 16

🥭 16

🍎 16

🫐 16

🍅 16

🌰 16

🥩 16

🍻 16

🥶 16

😏 16

🍏 15

🍐 15

🍑 15

🍒 15

🍓 15

🥝 15

🥑 15

🍆 15

🥕 15

🌶️ 15

🥦 15

🍄 15

🥖 15

🍞 15

🥞 15

🧀 15

🍸 15

🧉 15

🍌 14

🌽 14

🫑 14

🥒 14

🥬 14

🧄 14

🫘 14

🫓 14

🥐 14

🥯 14

🍔 14

🧇 14

🥂 14

🍹 14

🍷 14

🥤 14

🤧 14

😐 14

🌂 14

😲 13

🍊 13

🍋 13

🧅 13

🥨 13

🍗 13

🍖 13

🍾 13

🧋 13

🥃 13

🤪 13

🥰 13

🛬 13

🛫 13

🌈 13

🥓 12

🫥 12

💚 12

💛 12

🛑 12

🚦 12

🛸 12

🌀 12

😊 11

👵 11

💣 11

🛩️ 11

🥚 10

😗 10

🎁 9

🍳 9

🥇 9

㊗️ 9

💯 8

😻 8

🐱 8

🥘 7

🏅 7

🥈 7

㊙️ 7

🉑 7

🫡 7

👹 6

🐈‍⬛ 6

😃 6

👽 6

🗺️ 5

🇨🇳 5

🤑 5

👺 5

🙉 5

💀 5

🧟‍♂️ 4

🏌️‍♀️ 4

🏌️ 4

🏂 4

⛷️ 4

😼 3

🧑‍✈️ 3

ROb25l @ 2026-3-1 16:25:13

梦熊可以投题吗？
zxw1234567 LV 3 @ 2026-1-3 20:06:32

栈溢出

🕚 1

🕥 1

🕙 1

🕜 1

🕐 1

🕧 1

👎 1

🐩 1

🐅 1

🐮 1
FlowerAccepted LV 3 @ 2025-10-23 16:06:37

完成今日大学习

💀 1

👎 1
- FlowerAccepted LV 3 @ 2025-10-23 16:07:17
  
  完成今日完成今日大学习大学习
- FlowerAccepted LV 3 @ 2025-10-23 16:07:41
  
  @user:706 完成今日完成今日完成今日大学习大学习大学习
- FlowerAccepted LV 3 @ 2025-10-23 16:07:57
  
  @user:706 栈溢出
mediocre_ LV 4 @ 2025-10-3 16:26:36

/kel
xhhyj LV 3 @ 2025-9-13 18:42:07

我有一个自己的OJ，有兴趣的可以去OJ首页加QQ群，加上群主即可获得账号。

OJ地址：https://xjsoj.ac.cn

如果你无法访问，请加入QQ群
zezechoicec LV 2 @ 2025-9-10 21:36:31

🟠
zezechoicec LV 2 @ 2025-9-10 21:36:01

🥳

NewbieZZZ LV 2 @ 2025-9-9 22:44:21

https://oier.team/problems/J3E

https://www.luogu.com.cn/problem/P10997

n^3 暴力，but 没过样例（有思路，感觉是对的）

Analysis

本解中，交叉点表示的是这个格子左上角的那个点。规定最右侧的一排交叉点为 $(x,m+1)$ ，最下面一排用 $(n+1,y)$ 表示。

红橙与黄绿分割线和红黄与橙绿分割线会形成一个抽象的 X 形。

可设 $dp(i,l,r)$ 表示当前在第 $i$ 行，红橙/黄绿分割线在第 $l$ 列，红黄/橙绿分割线在第 $r$ 列的最大总和。同时设 $s_{i,j}$ 表示第 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

滚动后时空应该可以过 $500$ 。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;
}

~~我想给他完整的一生。~~

🚾 3

NewbieZZZ LV 2 @ 2025-9-9 22:46:20

~~应该就我一个来发求调的（~~

jiangguangshang @ 2025-8-19 20:04:47

？梦熊OJ证书过期了
chillchill @ 2025-8-10 11:53:43

$\Huge{qp}$
jasonyjm LV 3 @ 2025-8-3 11:14:03

hp
zxw1234567 LV 3 @ 2025-7-29 9:30:05

fc
zsy0226 LV 1 @ 2025-7-28 8:59:57

$\text{qp}$
听听 LV 3 @ 2025-7-24 18:33:09

大家都来洛谷吗？
HHC883 LV 3 @ 2025-7-23 14:28:38

yeah?
mediocre_ LV 4 @ 2025-7-6 21:25:15
已修改

1
mamabenma LV 2 @ 2025-7-2 22:42:01

喵~
jiangguangshang @ 2025-6-25 20:22:26

说句闲话：研究珂学的最好方法是

🇯🇵 4
jiangguangshang @ 2025-6-23 20:47:10

此贴≈洛谷灌水区
yzc001 LV 3 @ 2025-6-21 17:37:11

qp
danilewu @ 2025-6-17 19:50:29

666

🦍 3
jiangguangshang @ 2025-6-13 21:00:05

啊？

🏛️ 2
Kevin_ProMax LV 3 @ 2025-6-11 22:18:38

qp
a_computers @ 2025-6-10 21:01:28

qp
CSPAK_Wkc LV 2 @ 2025-6-4 20:06:51

qp 考古
BiTSetN10000 @ 2025-6-4 7:08:10

qp
鑫侠 LV 3 @ 2025-6-1 17:30:45

回望历史吧，孩子，感受洛阳铲的力量,并在力量的熏陶下“……”…… 好像我也说不出来什么了（一介洛谷难民）
鑫侠 LV 3 @ 2025-6-1 17:17:07

神前刘明
ikun_hyz @ 2025-5-31 21:34:34

hp
Ryanhao @ 2025-5-30 17:37:11

$\dfrac{2}{3}\times10^\infin$
奶龙 @ 2025-5-28 20:19:22

qp

but为啥其他的都被删除了
zhangshuchang111 @ 2025-5-18 10:27:48

qp
BennyT LV 3 @ 2025-5-5 13:58:55

qp
joyTT LV 3 @ 2025-5-4 15:09:58

厉害
zxw1234567 LV 3 @ 2025-5-2 17:32:12

666
scratch_szc LV 2 @ 2025-4-30 19:04:45

66666
Helloworld LV 3 @ 2025-4-28 20:27:33

qp
yuxuzhehuan LV 4 @ 2025-4-28 12:48:33

qp
OIer_wst LV 3 @ 2025-4-27 20:45:21

qp
jinminghao LV 3 @ 2025-4-26 21:35:05

qp
zxw1234567 LV 3 @ 2025-4-21 17:10:55

666

😇 6

😄 5

🙃 4

😉 4
juan2012 LV 3 @ 2025-4-20 19:10:17

论在哪里才能看到赛时答疑帖
凌绝 LV 3 @ 2025-4-12 15:49:01

111
wuxinlong @ 2025-4-10 17:03:24

怎么只剩这一个帖子了喵～

😇 5
- wuxinlong @ 2025-4-10 17:03:47
  
  尝试回复
liheyang LV 3 @ 2025-3-30 22:23:30

qp
sosczy @ 2025-3-29 12:48:14

qp
zhizhi_c @ 2025-3-27 23:00:57

笑了
114514nextOJ LV 3 @ 2025-3-23 17:53:32

MXOJ是Hydro吧
- imsunxinhao @ 2025-4-11 19:59:42
  
  确实是，可以看admin.oier.team
zxcvbnmm LV 3 @ 2025-3-15 22:56:04

前排

😃 1
Star_F LV 3 @ 2025-3-8 10:53:33

%%%