: 矩阵移动)
2024年9月GESP真题及题解(C++七级): 矩阵移动
题目描述
小杨有一个n × m n \times mn×m的矩阵，仅包含01?三种字符。矩阵的行从上到下编号依次为1 , 2 , … , n 1,2,\dots, n1,2,…,n，列从左到右编号依次为1 , 2 , … , m 1, 2, \dots, m1,2,…,m。小杨开始在矩阵的左上角( 1 , 1 ) (1,1)(1,1)，小杨只能向下或者向右移动，最终到达右下角( n , m ) (n, m)(n,m)时停止，在移动的过程中每经过一个字符1得分会增加一分（包括起点和终点），经过其它字符则分数不变。小杨的初始分数为0 00分。
小杨可以将矩阵中不超过x xx个字符?变为字符1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。
输入格式
第一行包含一个正整数t tt，代表测试用例组数，接下来是t tt组测试用例。对于每组测试用例，一共n + 1 n + 1n+1行。
第一行包含三个正整数n , m , x n, m, xn,m,x，含义如题面所示。
之后n nn行，每行一个长度为m mm的仅含01?的字符串。
输出格式
对于每组测试用例，输出一行一个整数，代表最优策略下小杨的得分最多是多少。
输入输出样例 1
输入 1
2 3 3 1 000 111 01? 3 3 1 000 ?0? 01?输出 1
4 2说明/提示
样例 1 解释
对于第二组测试用例，将( 2 , 1 ) (2,1)(2,1)或者( 3 , 3 ) (3,3)(3,3)变为1 11均是最优策略。
数据规模与约定
| 子任务编号 | 数据点占比 | t tt | n , m n,mn,m | x xx |
|---|---|---|---|---|
| 1 11 | 30 % 30\%30% | ≤ 5 \leq 5≤5 | ≤ 10 \le 10≤10 | = 1 =1=1 |
| 2 22 | 30 % 30\%30% | ≤ 10 \le 10≤10 | ≤ 500 \le 500≤500 | ≤ 30 \le 30≤30 |
| 3 33 | 40 % 40\%40% | ≤ 10 \le 10≤10 | ≤ 500 \le 500≤500 | ≤ 300 \le 300≤300 |
对全部的测试数据，保证1 ≤ t ≤ 10 1 \leq t \leq 101≤t≤10，1 ≤ n , m ≤ 500 1 \leq n,m \leq 5001≤n,m≤500，1 ≤ x ≤ 300 1 \leq x \leq 3001≤x≤300，保证所有测试用例n × m n \times mn×m的总和不超过2.5 × 10 5 2.5 \times 10^52.5×105。
思路分析
这是一个动态规划问题，需要在小杨从矩阵左上角到右下角的移动过程中，通过将不超过x个’?‘变为’1’来最大化得分。小杨只能向下或向右移动，每经过一个’1’（包括起点和终点）得一分。
动态规划思路
定义状态dp[i][j][k]表示从起点(1,1)走到位置(i,j)，且恰好修改了k个’?'变为’1’时能够获得的最大得分。
状态转移考虑两种情况：
- 从上方
(i-1,j)或左方(i,j-1)转移过来，不修改当前格子 - 如果当前格子是’?‘且还有修改次数，可以将其修改为’1’，从上方或左方转移并使用一次修改
由于小杨可以选择任意不超过x次修改，最终答案是max(dp[n][m][k])对所有0 ≤ k ≤ x。
代码实现
#include<bits/stdc++.h>usingnamespacestd;// 定义最大常量，比题目限制稍大避免越界constintMAXN=502;// 最大行数constintMAXM=502;// 最大列数constintMAXX=302;// 最大修改数// dp[i][j][k]表示走到(i,j)位置，已经修改了k个'?'时的最大得分intdp[MAXN][MAXM][MAXX];string s[MAXN];// 存储矩阵，每行一个字符串intmain(){intt;// 测试用例组数cin>>t;while(t--){// 处理每组测试用例intn,m,x;// 矩阵行数、列数、最大修改次数cin>>n>>m>>x;// 读取矩阵并调整下标从1开始for(inti=1;i<=n;i++){cin>>s[i];s[i]=" "+s[i];// 在字符串前加空格，使列下标从1开始}// 初始化DP数组为0（因为得分为非负整数）memset(dp,0,sizeof(dp));// 动态规划计算所有状态for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){for(intk=0;k<=x;k++){// 枚举可能的修改次数// 从上方(i-1,j)和左方(i,j-1)转移，取最大值作为前驱状态intfrom_above=dp[i-1][j][k];intfrom_left=dp[i][j-1][k];intbest_prev=max(from_above,from_left);// 情况1：不修改当前格子if(s[i][j]=='1'){// 当前格子是'1'，得分加1dp[i][j][k]=max(dp[i][j][k],1+best_prev);}else{// 当前格子是'0'或'?'但不修改，得分不变dp[i][j][k]=max(dp[i][j][k],best_prev);}// 情况2：如果当前格子是'?'且还有修改次数，可以选择修改它if(k>0&&s[i][j]=='?'){// 从修改次数为k-1的状态转移intbest_prev_mod=max(dp[i-1][j][k-1],dp[i][j-1][k-1]);// 修改当前格子变为'1'，得分加1dp[i][j][k]=max(dp[i][j][k],1+best_prev_mod);}}}}// 在所有可能的修改次数中寻找最大得分intans=0;for(intk=0;k<=x;k++){ans=max(ans,dp[n][m][k]);}cout<<ans<<endl;}return0;}功能分析
1. 数据结构设计
- 三维DP数组：
dp[i][j][k]记录状态值 - 字符串数组：存储原始矩阵，下标从1开始便于处理边界
2. 边界处理
- 数组下标从1开始，
dp[0][j][k]和dp[i][0][k]自然为0（未初始化部分） - 当
i=1且j=1时，best_prev为0，正确处理起点
3. 状态转移逻辑
- 对每个位置
(i,j)和每种修改次数k，考虑两种决策：- 不修改当前格子：从上方或左方继承相同修改次数的状态
- 修改当前格子（仅当格子为’?'且k>0）：从修改次数少1的状态转移
- 通过取max操作保证每一步都选择最优路径
4. 时间复杂度分析
- 时间复杂度：O(t × n × m × x)
- 空间复杂度：O(n × m × x)
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
)
