企业官网建设流程全解析

山东省建设备案网站审批表,深圳坪山网站建设,网站建设淘宝客模板,打广告2024年9月GESP真题及题解(C七级): 矩阵移动 题目描述 小杨有一个 nmn \times mnm 的矩阵#xff0c;仅包含 01? 三种字符。矩阵的行从上到下编号依次为 1,2,…,n1,2,\dots, n1,2,…,n#xff0c;列从左到右编号依次为 1,2,…,m1, 2, \dots, m1,2,…,m。小杨开始在矩阵的左上…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 1n1行。第一行包含三个正整数n , m , x n, m, xn,m,x含义如题面所示。之后n nn行每行一个长度为m mm的仅含01?的字符串。输出格式对于每组测试用例输出一行一个整数代表最优策略下小杨的得分最多是多少。输入输出样例 1输入 12 3 3 1 000 111 01? 3 3 1 000 ?0? 01?输出 14 2说明/提示样例 1 解释对于第二组测试用例将( 2 , 1 ) (2,1)(2,1)或者( 3 , 3 ) (3,3)(3,3)变为1 11均是最优策略。数据规模与约定子任务编号数据点占比t ttn , m n,mn,mx xx1 1130 % 30\%30%≤ 5 \leq 5≤5≤ 10 \le 10≤10 1 112 2230 % 30\%30%≤ 10 \le 10≤10≤ 500 \le 500≤500≤ 30 \le 30≤303 3340 % 40\%40%≤ 10 \le 10≤10≤ 500 \le 500≤500≤ 300 \le 300≤300对全部的测试数据保证1 ≤ t ≤ 10 1 \leq t \leq 101≤t≤101 ≤ n , m ≤ 500 1 \leq n,m \leq 5001≤n,m≤5001 ≤ 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。代码实现#includebits/stdc.husingnamespacestd;// 定义最大常量比题目限制稍大避免越界constintMAXN502;// 最大行数constintMAXM502;// 最大列数constintMAXX302;// 最大修改数// dp[i][j][k]表示走到(i,j)位置已经修改了k个?时的最大得分intdp[MAXN][MAXM][MAXX];string s[MAXN];// 存储矩阵每行一个字符串intmain(){intt;// 测试用例组数cint;while(t--){// 处理每组测试用例intn,m,x;// 矩阵行数、列数、最大修改次数cinnmx;// 读取矩阵并调整下标从1开始for(inti1;in;i){cins[i];s[i] s[i];// 在字符串前加空格使列下标从1开始}// 初始化DP数组为0因为得分为非负整数memset(dp,0,sizeof(dp));// 动态规划计算所有状态for(inti1;in;i){for(intj1;jm;j){for(intk0;kx;k){// 枚举可能的修改次数// 从上方(i-1,j)和左方(i,j-1)转移取最大值作为前驱状态intfrom_abovedp[i-1][j][k];intfrom_leftdp[i][j-1][k];intbest_prevmax(from_above,from_left);// 情况1不修改当前格子if(s[i][j]1){// 当前格子是1得分加1dp[i][j][k]max(dp[i][j][k],1best_prev);}else{// 当前格子是0或?但不修改得分不变dp[i][j][k]max(dp[i][j][k],best_prev);}// 情况2如果当前格子是?且还有修改次数可以选择修改它if(k0s[i][j]?){// 从修改次数为k-1的状态转移intbest_prev_modmax(dp[i-1][j][k-1],dp[i][j-1][k-1]);// 修改当前格子变为1得分加1dp[i][j][k]max(dp[i][j][k],1best_prev_mod);}}}}// 在所有可能的修改次数中寻找最大得分intans0;for(intk0;kx;k){ansmax(ans,dp[n][m][k]);}coutansendl;}return0;}功能分析1. 数据结构设计三维DP数组dp[i][j][k]记录状态值字符串数组存储原始矩阵下标从1开始便于处理边界2. 边界处理数组下标从1开始dp[0][j][k]和dp[i][0][k]自然为0未初始化部分当i1且j1时best_prev为0正确处理起点3. 状态转移逻辑对每个位置(i,j)和每种修改次数k考虑两种决策不修改当前格子从上方或左方继承相同修改次数的状态修改当前格子仅当格子为’?且k0从修改次数少1的状态转移通过取max操作保证每一步都选择最优路径4. 时间复杂度分析时间复杂度O(t × n × m × x)空间复杂度O(n × m × x)各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}