3904 - 矩阵移动（matrix）
题目描述
小杨有一个 n \times m的矩阵，仅包含 01? 三种字符。矩阵的行从上到下编号依次为 1,2,\dots,n，列从左到右编号依次为 1,2,\dots,m 编号。小杨开始在矩阵的左上角（1,1 ），小杨只能向下或者向右移动，最终到达右下角（ n,m）时停止，在移动的过程中每经过一个字符 1 得分会增加一分（包括起点和终点），经过其它字符则分数不变。小杨的初始分数为 0 分。
小杨可以将矩阵中不超过 x 个字符 ? 变为字符 1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。
输入
第一行包含一个正整数 t，代表测试用例组数。
接下来是 t组测试用例。对于每组测试用例，一共 n+1 行。
第一行包含三个正整数 n,m,x，含义如题面所示。
之后 n 行，每行包含一个长度为 m 且仅包含 01? 三种字符的字符串。
输出
对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。
样例
输入
2 3 3 1 000 111 01? 3 3 1 000 ?0? 01?
输出
4 2
输入
3 10 11 8 00?01???000 100????000? 01?0????1?0 00?0??101?1 1?0?010?001 ???0?00?0?0 ?1?0?0000?? 00?0?000?00 ?000000000? ?0000?000?1 12 5 10 00000 0?000 000?0 00000 00000 000?0 00000 00000 00000 00000 00100 00000 10 12 4 ?001?0?00000 1??10???0?10 00?0??0?0??1 00???0?0??11 0??0????0??? ???0100???00 ??100101???? 00??1?1????? ?01??0??0100 1??01?0??0??
输出
15 3 10
输入
4 11 12 7 0?00???0???0 0000?000?01? ?0000??????0 ?000000????0 ?00?00??0000 0??0000?00?0 0?0?0?0000?1 0001?????000 0??0000??000 ?000?1??0?01 ??000000???? 10 6 8 00?0?0 0010?0 ?000?? 00???? 0000?0 0000?0 ??0??0 001??? 0?000? 00??00 12 9 7 010101011 110010000 1?1000?1? 001111001 011011101 10??11010 00?100?00 0?110?100 011000??1 1?0?01?10 01000000? 0011?0101 9 9 1 001?00000 000?00000 0000??010 001000000 000010000 110000000 000000000 ?00?0000? 000000000
输出
10 9 17 4
说明
样例 1 解释
对于样例 1 的第二组测试用例，将 （2,1 ）或者 （ 3,3）变成 1 均是最优策略。
数据范围
对于全部数据，保证有 1 \le t \le 10,1 \le n,m \le 500, 1 \le x \le 300 ,同时保证所有测试用例 n\times m 的总和不超过 2.5 \times 10^5。
| 子任务编号 | 数据点占比 | t | n,m | x |
|---|---|---|---|---|
| 1 | 30\% | \le 5 | \le 10 | =1 |
| 2 | 30\% | \le 10 | \le 500 | \le 30 |
| 3 | 40\% | \le 10 | \le 500 | \le 300 |
来源
GESP 9月认证 C++ 七级真题
标签
