「COCI 2010.03.06」CHUCK

ID: 16164

传统题

1000ms

32MiB

难度: (无)

上传者:

标签>

2010

COCI

题目描述

译自 COCI 2010.03.06 T6. CHUCK

给你一个 $R$ 行 $C$ 列的矩阵 $A$ ， $|A_{i,j}|\leq 10^4$ 。请使用若干次下述操作（次数尽量少），使得矩阵中 $\sum_i \sum_j A_{i,j}$ 尽可能大。

操作	示例
$\texttt{rotR i k}$ 将第 $i$ 行的元素循环右移 $k$ 位	$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ rotR 3 1 }}\begin{pmatrix}1&2&3\\4&5&6\\9&7&8\\10&11&12\end{pmatrix}$
$\texttt{rotS j k}$ 将第 $j$ 列的元素循环下移 $k$ 位	$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ rotS 3 2 }}\begin{pmatrix}1&2&9\\4&5&12\\7&8&3\\10&11&6\end{pmatrix}$
$\texttt{negR i}$ 将第 $i$ 行的元素全部乘以 $-1$ 该操作当且仅当该行任何一个元素均未乘以 $-1$ 时有效	$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ negR 2 }}\begin{pmatrix}1&2&3\\-4&-5&-6\\7&8&9\\10&11&12\end{pmatrix}$
$\texttt{negS j}$ 将第 $j$ 列的元素全部乘以 $-1$ 该操作当且仅当该列任何一个元素均未乘以 $-1$ 时有效	$\begin{pmatrix}1&2&3\\0&0&0\\7&8&9\\10&11&12\end{pmatrix}\xrightarrow{\large\texttt{ negS 1 }}\begin{pmatrix}-1&2&3\\0&0&0\\-7&8&9\\-10&11&12\end{pmatrix}$

第一行： $R,C$ 。
接下来 $R$ 行：矩阵 $A$ 。

第一行包含两个整数，第一个整数为 $\sum_i \sum_j A_{i,j}$ 的最大值，第二个数为操作数量 $T$ 。
接下来 $T$ 行，每行包含一组操作。

3 4
1 -2 5 200
-8 0 -4 -10
11 4 0 100

345 2
rotS 2 1
negR 2

34 4
rotR 1 1
rotS 3 1
negR 2
negR 3

$1≤R,C≤100,$ $|A_{i,j}|≤10^4$ 。

若你求了个错误的最大和，或是执行的操作中有无效的，该测试点不得分，否则：