矩阵移动

题目描述

⼩杨有⼀个有⼀个 的矩阵，仅包含 01? 三种字符。矩阵的⾏从上到下编号依次为 ，列从左到右编号 依次为 编号。⼩杨开始在矩阵的左上角（ ），⼩杨只能向下或者向右移动，最终到达右下角（ ） 时停⽌，在移动的过程中每经过⼀个字符 1 得分会增加⼀分（包括起点和终点），经过其它字符则分数不变。⼩杨 的初始分数为 分。 ⼩杨可以将矩阵中不超过 个字符 ? 变为字符 1。⼩杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想 知道⾃⼰最多能获得多少分。

输入格式

第⼀⾏包含⼀个正整数 ，代表测试⽤例组数。 接下来是 组测试⽤例。对于每组测试⽤例，⼀共 ⾏。 第⼀⾏包含三个正整数 ，含义如题⾯所⽰。 之后 ⾏，每⾏包含⼀个长度为 且仅包含 01? 三种字符的字符串。

输出格式

对于每组测试⽤例，输出⼀⾏⼀个整数，代表最优策略下⼩杨的得分最多是多少。 3.2.4 样例1 1 2 2 3 3 1 3 000 4 111 5 01? 6 3 3 1 7 000 8 ?0? 9 01? 1 4 2 2 对于第⼆组测试⽤例，将（ ）或者 （ ）变成 均是最优策略。 子任务编号 数据点占比 1 30% 2 30% 3 40% 对于全部数据，保证有 ， ，同时保证所有测试⽤例 的总和不超过 。 3.2.5 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 505; 4 int dp[N][1005]; 5 char a[N][N]; 6 int n, m, x; 7 int main(){ 8 int t; 9 scanf("%d", &t); 10 while(t--){ 11 scanf("%d%d%d", &n, &m, &x); 12 for(int i = 1; i <= m; i++) for(int j = 0; j <= x; j++) dp[i][j] = 0; 13 for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1); 14 for(int i = 1; i <= n; i++){ 15 for(int j = 1; j <= m; j++){ 16 for(int k = x; k>=0; k--){ 17 if(a[i][j] == '1') 18 dp[j][k] = max(dp[j][k], dp[j - 1][k]) + 1; 19 if(a[i][j] == '0') 20 dp[j][k] = max(dp[j][k], dp[j - 1][k]); 21 if(a[i][j] == '?') { 22 if(!k) dp[j][k] = max(dp[j][k], dp[j - 1][k]); 23 else dp[j][k] = max(max(dp[j][k], dp[j - 1][k]), max(dp[j][k

• 1], dp[j - 1][k - 1]) + 1); 24 } 25 } 26 } 27 } 28 int ans = 0; 29 for(int k = 0; k <= x; k++) ans = max(ans, dp[m][k]); 30 printf("%d\n", ans); 31 } 32 33 }

样例输入 #1

1 2
2 3 3 1
3 000
4 111
5 01?
6 3 3 1
7 000
8 ?0?
9 01?
1 4
2 2
对于第⼆组测试⽤例，将（ ）或者 （ ）变成 均是最优策略。
子任务编号 数据点占比
1 30%
2 30%
3 40%
对于全部数据，保证有 ， ，同时保证所有测试⽤例 的总和不超过
。

样例输出 #1

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。