你好，梦熊 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。

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

已修改
763 次查看
举报

🎉 100

🤫 54

👻 43

🤠 41

🍭 41

🙊 39

🙃 33

😀 30

🐒 26

😚 25

🐈 25

😍 24

😄 24

6️⃣ 23

☺️ 22

😪 22

😉 21

😅 21

😥 21

😢 21

😆 21

😫 20

💥 20

😦 19

💟 19

💝 19

🫠 19

💔 19

🐯 19

☠️ 19

😣 18

😨 18

🦅 18

🐣 18

🙂 18

🤭 18

🥺 17

❤️‍🔥 17

🧡 17

😁 17

😘 17

🤤 17

🥸 17

🤖 17

😸 17

😹 17

🦌 17

🦓 17

🦆 17

🏈 17

☣️ 17

🤨 17

😑 17

😜 17

🤮 16

💖 16

🪶 16

🎋 16

🐗 16

🐅 16

🌏 16

🇮🇳 16

🥜 16

🦚 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

🍇 13

🫐 13

🥝 13

🥑 13

🥕 13

🥬 13

🧄 13

🫘 13

🥖 13

🧀 13

🍸 13

🧉 13

🌂 13

🍌 12

🍑 12

🍆 12

🌽 12

🌶️ 12

🫑 12

🥒 12

🧅 12

🥨 12

🫓 12

🥐 12

🍞 12

🥯 12

🥞 12

🧇 12

🍾 12

🥂 12

🍹 12

🍷 12

🥤 12

🤧 12

🤪 12

😐 12

🍊 11

🍋 11

🍔 11

🥓 11

🍗 11

🍖 11

🧋 11

🥃 11

🫥 11

🥰 11

💚 11

💛 11

🛬 11

🛫 11

😲 10

👵 10

💣 10

🛑 10

🚦 10

🛸 10

🌀 10

🌈 10

😊 9

🛩️ 9

🥚 8

🍳 7

😗 7

🎁 6

💯 6

🥇 6

㊗️ 6

🥘 5

🏅 5

🐱 5

🉑 5

👹 4

🗺️ 4

🥈 4

😻 4

🐈‍⬛ 4

㊙️ 4

🫡 4

😃 3

🇨🇳 3

🙉 3

👽 3

💀 3

🤑 2

👺 2

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

完成今日大学习

💀 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

%%%
清空 LV 2 @ 2025-3-3 20:57:55

后排
WsW @ 2025-3-2 16:25:19

试图回复