矩阵移动 时间限制: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? 三种字符的字符串。
输出格式
对于每组测试用例,输出一行一个整数,代表最优策略下小杨的得分最多是多少。
输入样例
输出样例
对于第二组测试用例,将(1,1)或者 (3,3)变成 1 均是最优策略。

对于全部数据,保证有1≤t≤10,1≤n,m≤500,1≤x≤300,同时保证所有测试用例 n×m 的总和不超过 2.5×105。
如果不考虑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,则不可增加修改次数。
可以观察到每一行的计算只依赖于上一行的信息,第一维可以优化,故可以使用滚动数组对数组进行降维。