CF-1078-D. Table Cut（绷不住了，真是贪心了，贪了） · znzryb
## 题目大意
给定一个大小为$n \times m$的表格，其中每个单元格包含$0$或$1$。任务是通过一条从左上角到右下角的切割线将其分成两部分。切割线只能向右或向下走。
设$a$为切割后表格一部分中的1的数量，$b$为表格另一部分中的1的数量。目标是最大化$a \cdot b$的值。
**输入**
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。随后是测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 3 \cdot 10^{5}$, $2 \leq n \cdot m \leq 3 \cdot 10^{5}$) — 表中的行数和列数。
接下来的 $n$ 行中，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数对应值为 $a_{i, j}$ ($0 \leq a_{i, j} \leq 1$)。
保证所有测试用例中 $n \cdot m$ 的总和不超过 $3 \cdot 10^{5}$。
**输出**
对于每个测试用例，在输出数据的第一行输出一个数字 - 乘积的最大值。
在第二行，输出一个由 $n$ 个字符 'D' 和 $m$ 个字符 'R' 组成的字符串，表示下一次切割的方向，其中 'D' 表示向下切割，而 'R' 表示向右切割。
```cpp
3
5 5
1 0 1 1 0
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
0 0 0 0 1
5 4
0 0 1 0
0 1 1 1
1 0 0 1
0 1 0 1
0 0 1 0
3 2
1 0
0 1
1 1
```
```cpp
30
RDRDRDRDDR
20
DRRDRDDDR
4
DRDRD
```
**注意**
这些图片展示了第一个和第二个测试用例的正确切割方式，从而实现产品的最大价值。
.png)
.png)
## 思路讲解
绷不住了，我想了半天的DP解法，结果和我讲，其实这道题目根本不用DP，就贪心啊，然后这个答案总归是最大的，就是**把它尽量均匀的切分成两半，总是可以的**。
就**是形如上图这样子切分**，可以证明啊，其实也不用证明了。你直接感觉你就知道把它们尽量均匀的切分成两半是非常可行的，是完全可行的。
```cpp
for (int x=1;x<=N;++x) {
ll to_sum=sum+pre_sum[x][M];
// #ifdef LOCAL
// debug(to_sum);
// debug(sum);
// #endif
if (to_sum>=half && !is_in) {
ll bpy=1;
is_in=true;
for (ll y=M;y>=1;--y) {
sum+=maze[x][y];
if (sum==half) {
bpy=y;
break;
}
}
for (int y=1;y<bpy;++y) {
ans.push_back('R');
}
ans.push_back('D');
for (int y=bpy;y<=M;++y) {
ans.push_back('R');
}
}else {
ans.push_back('D');
}
sum=to_sum;
}
```
## AC代码
AC
[https://codeforces.com/contest/2194/submission/362089758](https://codeforces.com/contest/2194/submission/362089758)
**源代码**
```cpp
/**
* Problem: D. Table Cut
* Contest: Codeforces Round 1078 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2194/problem/D
* Created: 2026-02-09 14:03:01
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N,M;
cin >> N >> M;
vector<vector<int>> maze(N+2,vector<int>(M+2));
vector<vector<ll>> pre_sum(N+2,vector<ll>(M+2));
ll sum1=0;
for (int x=1;x<=N;++x) {
for (int y=1;y<=M;++y) {
cin>>maze[x][y];
sum1+=maze[x][y];
}
}
string ans;
for (int x=1;x<=N;++x) {
partial_sum(all(maze[x]),pre_sum[x].begin());
}
ll sum=0,half=sum1/2;
bool is_in=false;
for (int x=1;x<=N;++x) {
ll to_sum=sum+pre_sum[x][M];
// #ifdef LOCAL
// debug(to_sum);
// debug(sum);
// #endif
if (to_sum>=half && !is_in) {
ll bpy=1;
is_in=true;
for (ll y=M;y>=1;--y) {
sum+=maze[x][y];
if (sum==half) {
bpy=y;
break;
}
}
for (int y=1;y<bpy;++y) {
ans.push_back('R');
}
ans.push_back('D');
for (int y=bpy;y<=M;++y) {
ans.push_back('R');
}
}else {
ans.push_back('D');
}
sum=to_sum;
}
ll a=sum1/2,b=sum1-a;
cout<<a*b<<"\n";
cout<<ans<<"\n";
#ifdef LOCAL // 校验器
if (count(all(ans),'D')==N && count(all(ans),'R')==M) {
}else {
cout<<"WA\n";
return;
}
ll col=0,row=0;
ll a_num=0,b_num=0;
for (auto ch:ans) {
if (ch=='R') {
++col;
}else {
row++;
a_num+=pre_sum[row][col];
b_num+=pre_sum[row][M]-pre_sum[row][col];
}
}
if (a_num*b_num==a*b) {
}else {
cout<<"WA\n";
}
#endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2194/submission/362089758
DRDRRD
1
3 2
1 0
0 1
1 1
_______________[ Stress test, testcase 16 INPUT ]_______________
1
1 4
0 0 0 1
_______________[ Stress test, testcase 16 OUTPUT]_______________
0
DRRRRR
WA
*/
```
## 心路历程（WA，TLE，MLE……）