AT_abc407_g.[ABC407G] Domino Covering SUM

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个 $H$ 行 $W$ 列的网格，第 $i$ 行第 $j$ 列的格子上写有数字 $A_{i,j}$ 。

你要在网格上摆放若干个多米诺骨牌，每个骨牌盖住相邻的两个格子。你要保证没有任何一个格子被多于一个骨牌盖住。

求摆放完骨牌之后，所有没有被骨牌盖住的格子上的数字之和的最大值。

输入格式

第一行两个整数 $H,W(H,W\ge 1,H\times W\le 2000)$ 。
接下来 $H$ 行，每行 $W$ 个整数表示 $A(-10^{12}\le A_{i,j}\le 10^{12})$ 。

输出格式

一行一个整数表示答案。

输入输出样例

输入#1
```
3 4
3 -1 -4 1
-5 9 -2 -6
-5 3 -5 8
```
输出#1
```
23
```

输入#2

5 5
-70 11 -45 -54 -30
-99 39 -83 -69 -77
-48 -21 -43 -96 -24
-54 -65 21 -88 -44
-90 -33 -67 -29 -62

输出#2

输入#3

8 9
-74832 16944 58683 32965 97236 -52995 43262 -51959 40883
-58715 13846 24919 65627 -11492 -63264 29966 -98452 -75577
40415 77202 15542 -50602 83295 85415 -35304 46520 -38742
37482 56721 -38521 63127 55608 95115 42893 10484 70510
53019 40623 25885 -10246 70973 32528 -33423 19322 52097
79880 74931 -58277 -33783 91022 -53003 11085 -65924 -63548
78622 -77307 81181 46875 -81091 63881 11160 -82217 -55492
62770 39530 -95923 92440 -69899 77737 89392 -14281 84899

输出#3

说明/提示

样例解释 1

网格如下所示：

以下的摆放方式中未被盖住的数字之和为 $23$ 。

可以证明此值无法达到 $24$ 或更大，故输出 $23$ 。

By @chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页