P10865 [HBCPC2024] Genshin Impact Startup Forbidden III题目描述Blue-edged Shot 被 LeavingZ 禁止玩《原神》。然而今天 LeavingZ 前往了华中科技大学的网络科学与工程学院参加2024年中国湖北省国际大学生程序设计竞赛并收获了金牌。《原神》中的一个活动嘟嘟可砰砰历险记已经开始了。这是一个单人游戏每局游戏都涉及一个池塘。池塘可以被划分为一个n×mn×mn×m的网格其中第iii行第jjj列的单元格表示为(i,j)(i,j)(i,j)。在这些单元格中有kkk个单元格包含鱼你将扮演火花骑士可莉她用炸药来捕鱼。如果可莉在(a,b)(a,b)(a,b)位置投放炸弹那么所有满足∣x−a∣∣y−b∣≤1|x-a||y-b|\le 1∣x−a∣∣y−b∣≤1的单元格(x,y)(x,y)(x,y)都将被爆炸覆盖。对于每一个被爆炸覆盖的单元格可莉都会从其中捕到一条鱼。可莉可以在任何位置投放炸弹。问题是为了捕到所有的鱼至少需要多少枚“蹦蹦炸弹”输入格式第一行包含三个整数n,m,kn,m,kn,m,k(1≤n,m≤103,1≤k≤101 \le n,m \le 10^3, 1 \le k \le 101≤n,m≤103,1≤k≤10)分别表示网格的大小行数和列数以及包含鱼的单元格数量。接下来的kkk行每行包含三个整数xi,yi,aix_i,y_i,a_ixi,yi,ai(1≤xi≤n,1≤yi≤m,1≤ai≤31\le x_i \le n, 1 \le y_i \le m, 1 \le a_i \le 31≤xi≤n,1≤yi≤m,1≤ai≤3)表示在网格的 (xi,yix_i, y_ixi,yi) 单元格中有aia_iai条鱼。输入保证所有的(xi,yi)(x_i, y_i)(xi,yi)单元格坐标都是唯一的。输出格式输出一个整数表示所需的最少炸弹数量。在这个问题中你需要计算并输出一个整数该整数代表为了捕获所有鱼所需投放的最少“蹦蹦炸弹”数量。输入输出样例 #1输入 #15 5 3 1 1 2 2 2 1 5 5 2输出 #14说明/提示一种可能的方法是在(1,2)(1,2)(1,2)位置投放两枚炸弹再在(5,5)(5,5)(5,5)位置投放另外两枚炸弹。可以证明没有比这个答案更小的解。C实现#includebits/stdc.h#defineinit(x)memset(x,INF,sizeof(x))#definelllonglong#defineINF0x3f3f3f3fusingnamespacestd;constintMAX2e65;constintMOD1e97;inlineintread();intn,m,k,p,tot,v[15],dp[MAX],sx[]{0,1,-1,0,0},sy[]{0,0,0,1,-1};vectorinttmp;setpairint,intloc;mappairint,int,intid;intmain(){nread();mread();kread();for(inti0;ik;i){intxread(),yread();v[i]read();id[{x,y}]i;//用 map 记录下对应的位置for(intj0;j5;j){intxxxsx[j],yyysy[j];if(1xxxxn1yyyym)loc.insert({xx,yy});//预处理出炸弹可能放置的位置用 set 去重}tottot*4v[i];//处理出对应的四进制数}init(dp);dp[0]0;for(inti0;i(1(2*k));i){if(dp[i]INF)continue;for(autonxt:loc){intxnxt.first,ynxt.second;pi;tmp.clear();for(intj1;jk;j)tmp.push_back(p%4),p/4;//逐位分离for(intj0;j5;j){intxxxsx[j],yyysy[j];if(id.find({xx,yy})id.end())continue;//不需要放置炸弹intoid[{xx,yy}];tmp[k-o-1]min(v[o],tmp[k-o-1]1);//炸弹最多不超过格子中鱼的数量 注意下标}p0;for(intitmp.size()-1;~i;--i)pp*4tmp[i];//重新计算出新的状态dp[p]min(dp[p],dp[i]1);}}printf(%d\n,dp[tot]);return0;}inlineintread(){ints0;intf1;charchgetchar();while((ch0||ch9)ch!EOF){if(ch-)f-1;chgetchar();}while(ch0ch9){ss*10ch-0;chgetchar();}returns*f;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容