2274 . 割韭菜
TopCoder
Tags
Description
東門大地主喜歡割韭菜。
韭菜們排成一個 $n \times m$ 的矩形，從上數來第 $i$ 橫列、由左數來第 $j$ 直行的方格內有一個數字 $a_{ij}$，代表割掉這株韭菜的爽度。東門大地主每次可以割掉「尚未被割的韭菜們形成的矩形」的其中一個邊上（也就是左邊、右邊、上面、下面擇一）的所有韭菜們，而這次割韭菜行動的爽度就是該次被割掉的韭菜的爽度總和；而割完所有韭菜的爽度則是每一次操作的爽度的最大值。
現在，給你韭菜們的爽度，你知道要怎麼割會最爽（爽度最高）嗎？
Input Format
第一行有兩個整數 $n, m$，符合 $1 \leq n, m \leq 1500$
接下來 $n$ 行每行有 $m$ 個整數 $a_{ij}$ ，符合 $-10 ^ 9 \leq a_{ij} \leq 10 ^ 9$。
Output Format
第一行輸出一次操作的最大爽度，第二行輸出一個由 LRUD 四種字元組成的字串，代表每次要割掉韭菜的最左/右/上/下排（定義輸入中第一行最左邊的數字為表格左上角）。按照此字串的步驟執行完之後，所有數字都必須被刪除，且最大爽度的一次操作必須是所有方法中最大的。
若有多種可能的答案，任意一種都會算是對的。
Sample Input 1
3 3
4 -2 5
-10 3 6
4 7 -10
4 -2 5
-10 3 6
4 7 -10
Sample Output 1
11
LLDR
LLDR
Sample Input 2
2 3
-5 -4 -3
-4 -1 -8
-5 -4 -3
-4 -1 -8
Sample Output 2
-1
URRD
URRD
Hints
範例測資一解釋：對於字串"LLDR"，四次收割的爽度分別是 $-2, 8, -10, 11$，其中最大值是 $11$ ，而這也是所有方法中最大的。若第二行輸出 "RDUU" 也會被算為正確。
由於本題輸入量較大，建議使用 scanf/printf 或是使用 cin/cout並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);以加快輸入的速度。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~6 | $a_i \ge 0$ | 7 |
| 3 | 7~16 | $n, m\le30$ | 25 |
| 4 | 7~26 | $n, m\le 300$ | 22 |
| 5 | 2~31 | 無其他限制 | 46 |