#CF2122A. 贪婪网格
贪婪网格
明白了,你希望把题面中所有独立成行的公式(包括矩阵、条件说明、算式等)都用 $$ 或 \[ \] 包裹起来,而不是混用行内 $...$。
下面是修改后的完整题面(仅公式部分改为独立成行,其余文字不变):
A. 贪婪网格
时间限制:1 秒
内存限制:256 兆字节
在网格中,如果一条路径从左上角单元格出发,且只能向右或向下移动,并且总是移动到数值更大的相邻单元格(若相等则可任选其一),则称其为贪婪路径。
路径的值定义为路径所经过单元格(包括起点和终点)的数值之和。
是否存在一个由非负整数构成的 网格,使得没有一条贪婪路径能达到所有向下/向右路径中的最大值?
输入
每个测试文件包含多个测试用例。第一行包含测试用例数 ()。
每个测试用例的描述独占一行,包含两个整数 (),分别表示网格的行数和列数。
输出
对于每个测试用例,输出一行,若所需网格存在则输出 "YES",否则输出 "NO"。
答案大小写不敏感(例如 "yEs"、"yes"、"Yes"、"YES" 均视为肯定回答)。
样例
输入
2
3 3
1 2
输出
YES
NO
说明
在第一个测试用例中,网格的一个例子为:
用 表示第 行第 列单元格的值。
所有向下/向右路径的最大值为
$$a_{1,1} + a_{2,1} + a_{3,1} + a_{3,2} + a_{3,3} = 17. $$该路径不是贪婪的,因为 ,因此贪婪路径的第一步必须向右移动。
贪婪路径的最大值为
$$a_{1,1} + a_{1,2} + a_{2,2} + a_{3,2} + a_{3,3} = 16. $$在第二个测试用例中,可以证明不存在满足条件的网格。