A30334. 矩阵移动
填空题
困难
知识点
题目描述
矩阵移动
题目描述
小杨有一个有一个 n * m 的矩阵，仅包含 01? 三种字符。矩阵的行从上到下编号依次为1,2,,,,,,n ，列从左到右编号依次为1,2,,,,,,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?
1
输出样例
4
2
对于第二组测试用例，将（1,）或者 （3,1）变成 均是最优策略。
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int dp[N][1005];
char a[N][N];
int n, m, x;
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &x);
for (int i = 1; i <= m; i++) for (int j = 0; j <= x; j++) dp[i][j] = 0;
for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = x; k>=0; k--) {
if(a[i][j] == '1')
dp[j][k] = max(dp[j][k], dp[j - 1][k]) + 1;
if(a[i][j] == '0')
dp[j][k] = max(dp[j][k], dp[j - 1][k]);
if(a[i][j] == '?') {
if(!k) dp[j][k] = max(dp[j][k], dp[j - 1][k]); else dp[j][k] = max(max(dp[j][k], dp[j - 1][k]), max(dp[j][k
- 1], dp[j - 1][k - 1]) + 1);
}
}
}
}
int ans = 0;
for (int k = 0; k <= x; k++) ans = max(ans, dp[m][k]);
printf("%d\n", ans);
}
}
上一题
下一题