题解 P12135 [蓝桥杯 2025 省 B] 水质检测
我不会贪婪证明，但是我们可以用动态规划的思想来写这道题，为什么可以呢？因为每一个点只会由前一个位置的情况来决定当前本身的情况。我们设 d p i , j dp_{i,j} dpi,j 表现为第 i i i 位置，第 j j j 个位置确定添补 # 而且包管和前面联通的最小花费， j j j 取 0 0 0 或 1 1 1，分别表现 i i i 位置的上层还是下层。
由上面的图，我们可以看到，当前如果为 #，要么由前面那个直接转移(路径①)，要么就由前面另一个方向转移(路径②)。我们设蓝色所在位置为 ( i , 0 ) (i,0) (i,0) 。
- 那么路径①就是由前面 ( i − 1 , 1 ) (i-1,1) (i−1,1) 转移到 ( i , 0 ) (i,0) (i,0)。
- 那么路径②就是由前面 ( i − 1 , 1 ) (i-1,1) (i−1,1) 先转移到 ( i , 1 ) (i,1) (i,1) 再转移到 ( i , 0 ) (i,0) (i,0) 。
我们可以根据上面所计划的 d p dp dp 状态可以知道，路径①只会只由前面 ( i − 1 , 0 ) (i-1,0) (i−1,0) 确定，而当前这个点已经包管了为 # 且与前面联通，而且花费最小，那么我们只需要考虑 ( i , 0 ) (i,0) (i,0) 这一位是否为 # 即可，如果不为 # 则需要贡献加 1 1 1，否则直接转移。
而对于路径②，我们当然不可以直接由 ( i , 1 ) (i,1) (i,1) 转移，我们就需要考虑 ( i − 1 , 1 ) (i-1,1) (i−1,1)，因为这个点的 d p dp dp 值包管了它此时为 # 且与前面联通，而且花费最小，那么，如果要通过路径②转移的话，我们就要考虑到 ( i , 1 ) (i,1) (i,1) 是否为 #，而且还需要考虑到 ( i , 0 ) (i,0) (i,0) 这一个是否为 #，即可盘算出对应的 d p dp dp 值。
对于下层的话，类比上层的做法一样可以求解，可以本身模仿试一下。
所以，我们可以得到最终的转移方程如下：
d p i , 0 = min ( d p i − 1 , 0 , d p i − 1 , 1 + ( s i , 1 ≠ # ) ) + ( s i , 0 ≠ # ) dp_{i,0} = \min(dp_{i-1,0}, dp_{i-1,1} + (s_{i,1} \neq \#)) + (s_{i,0} \neq \#) dpi,0=min(dpi−1,0,dpi−1,1+(si,1=#))+(si,0=#)
d p i , 1 = min ( d p i − 1 , 1 , d p i − 1 , 0 + ( s i , 0 ≠ # ) ) + ( s i , 1 ≠ # ) dp_{i,1} = \min(dp_{i-1,1}, dp_{i-1,0} + (s_{i,0}\neq \#)) + (s_{i,1} \neq \#) dpi,1=min(dpi−1,1,dpi−1,0+(si,0=#))+(si,1=#)
a n s = min ( d p e n d , 0 , d p e n d , 1 ) ans=\min(dp_{end,0},dp_{end,1}) ans=min(dpend,0,dpend,1)
我们得到了一个转移方程，此中 s i , j s_{i,j} si,j 表现的是 i i i 位置对应的上下层字符， j j j 取 0 , 1 0,1 0,1， 0 0 0 为上层， 1 1 1 为下层。但是现在另有一个问题就是，如果从最开始进行 d p dp dp 转移，由于第 i i i 位置之前如果没有检测器，我们是不需要添加额外的检测器，所以我们需要找到第一个存在检测器的位置，以及末了一个位置的检测器位置即可。如果都找不到，阐明没有检测器，虽然标题说了，已经存在一些检测器，我们为安全起见，可以特判一下这个情况。末了的答案，肯定就是由末端的情况的最小值啦~，复杂度为 O ( n ) O(n) O(n)。
对于 d p dp dp 的初始值，只需要看当前是否为 #，为 # 则是 0 0 0，否则是 1 1 1 即可，然后就可以美美地敲一发 A C AC AC 啦~
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e6+30;
- char s[N][2];
- int dp[N][2]; // 表示当前 i 位第 j 个位置为 '#' 联通时候的最小花费
- void solve(){
- string t;
- int n;
- // 数据输入
- for(int j=0;j<2;j++){
- cin>>t;// 读入一个字符串
- n = t.size();
- for(int i=1;i<=n;i++)s[i][j] = t[i-1];
- }
- int st = n+1,en = 0; // 找到左右两边的起始位置
- for(int i=1;i<=n;i++){
- if(s[i][0]=='#'||s[i][1]=='#'){
- st = min(i,st);
- en = max(en,i);
- }
- }
- // 没有找到 '#' 直接返回即可
- if(st==n+1){
- cout<<0<<endl;
- return;
- }
- if(s[st][0]!='#')dp[st][0]=1;
- if(s[st][1]!='#')dp[st][1]=1;
- for(int i=st+1;i<=en;i++){
- dp[i][0] = min(dp[i-1][0],dp[i-1][1]+(s[i][1]!='#'))+(s[i][0]!='#');
- dp[i][1] = min(dp[i-1][1],dp[i-1][0]+(s[i][0]!='#'))+(s[i][1]!='#');
- }
- cout<<min(dp[en][0],dp[en][1])<<endl;
- }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- solve();
- return 0;
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
