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

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

已修改
753 次查看
举报

🎉 96

🤫 52

👻 41

🤠 40

🍭 40

🙊 37

🙃 32

😀 29

🐒 25

😚 24

🐈 24

😍 23

😄 23

6️⃣ 22

😪 21

😉 20

😅 20

☺️ 20

😥 20

😢 19

😫 19

😆 19

💥 18

😨 17

😦 17

💟 17

💝 17

🫠 17

💔 17

🐯 17

🙂 17

🤭 17

😣 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

🦚 14

☘️ 14

🐗 14

🐅 14

🐶 14

🦊 14

😇 14

🌏 14

🥢 14

😏 14

🏧 13

🍈 13

🍏 13

🍐 13

🍒 13

🥦 13

🍄 13

🥶 13

🤢 13

🍉 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

🧇 11

🍾 11

🥂 11

🍸 11

🥤 11

🧉 11

🍊 10

🍋 10

🍆 10

🌽 10

🌶️ 10

🫑 10

🥒 10

🥞 10

🍔 10

🥓 10

🍗 10

🍖 10

🍹 10

🍷 10

🧋 10

🥃 10

🫥 10

🤧 10

🤪 10

🥰 10

😐 10

😲 9

👵 9

💚 9

💛 9

💣 9

🛑 9

🚦 9

🛸 9

🛬 9

🛫 9

🌈 9

😊 8

🛩️ 8

🌀 8

🥚 6

🍳 5

😗 5

💯 5

🎁 4

🥇 4

㊗️ 4

🉑 4

🥘 3

👹 3

🗺️ 3

🏅 3

🥈 3

😻 3

🐱 3

🐈‍⬛ 3

㊙️ 3

😃 2

🇨🇳 1

🫡 1

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

😇 5

😄 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

试图回复
__0__ @ 2025-3-1 20:26:04

后排落座，不要吵闹。

轻轻一踢，踢爆前排。

往前一座，我即前排。