简答题 偏难
#20862

矩阵移动 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个有一个 n×m 的矩阵,仅包含 01? 三种字符。矩阵的行从上到下编号依次为1,…

矩阵移动

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个有一个 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?

输出样例

4
2

对于第二组测试用例,将(1,1)或者 (3,3)变成 1 均是最优策略。

对于全部数据,保证有1≤t≤10,1≤n,m≤500,1≤x≤300,同时保证所有测试用例 n×m 的总和不超过 2.5×105。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; 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", &amp;t); while(t--){ scanf("%d%d%d", &amp;n, &amp;m, &amp;x); for(int i = 1; i &lt;= m; i++) for(int j = 0; j &lt;= x; j++) dp[i][j] = 0; for(int i = 1; i &lt;= n; i++) scanf("%s", a[i] + 1); for(int i = 1; i &lt;= n; i++){ for(int j = 1; j &lt;= m; j++){ for(int k = x; k&gt;=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 &lt;= x; k++) ans = max(ans, dp[m][k]); printf("%d\n", ans); } }</pre>
解析

如果不考虑x,问题转换成为从(1,1)到(n,m)只能向下或者向右移动最多拿到多少个1。对于矩阵中的任意一点(i,j)只可能从(i-1,j)或者(i,j-1)移动过来。

状态设计:dp[i][j]表示到达位置(i,j)时可以获得的最大分数。

不难得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (a[i][j] == ‘1’?1:0)。

考了加入x,还是只能向下或者向右移动,之前只有1对结果有贡献,现在?也对结果有贡献。由于x的限制,?不能无限制的修改成1,所以需要记录修改次数。设计状态时增加一维表示修改次数。

状态设计:dp[i][j][k]表示到达位置(i,j)时,已经修改了k个字符所能获得的最大分数。

如果a[i][j]是0或者1,正常转移,和不考虑x时的转移过程一致,如果a[i][j]是?,先考虑当前有没有修改次数,如果没有当前阶段拿到和1和上一阶段比较求最大值,如果有修改次数,,需要看之前修改转移的值是多少,求最大值。

当a[i][j] == 1时,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+1,

当a[i][j] == 0时,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

当a[i][j] == ?时,如果没有修改次数,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

如果有修改次数,再考虑改或不改。

若修改当前节点为1,则有dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1,

若不修改,则有dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

取以上情况的最大值即可,同时需要考虑,若k==x,则不可增加修改次数。

可以观察到每一行的计算只依赖于上一行的信息,第一维可以优化,故可以使用滚动数组对数组进行降维。