题目要求在一个2×n的河床上增加最少的检测器，使得所有检测器互相连通。河床用一个2×n的字符矩阵表示，其中'#'表示已有检测器，'.'表示空白位置。如果两个检测器上下或左右相邻，则它们互相连通，且连通具有传递性。
这道题目可以使用动态规划来解决。我们需要考虑如何让所有检测器连通，并且使新增的检测器数量最少。
状态定义
我们定义状态dp[i][j]表示：当处理到第i列，且第i列的第j行为'#'（无论是原有的还是新放置的），并且前i列的所有检测器都连通时，需要新增的最少检测器数量。
其中：
i表示列号，范围是[st, en]，st是最左边有检测器的列，en是最右边有检测器的列
j表示行号，取值为0或1，分别表示第一行和第二行
状态转移
对于位置(i,j)，我们有两种可能的转移来源：
从(i-1,j)转移：即上一列同一行的位置
从(i-1,1-j)转移：即上一列不同行的位置，但这需要通过当前列的另一行(i,1-j)连接
下面用图示来说明状态转移：
列i-1 列i
□ ---- □ (行0)
| |
□ ---- □ (行1)
假设我们当前要计算dp[i][0]（即列i 行0的状态）：
从
dp[i-1][0]转移：
列i-1 列i
# ---- # (行0)
| |
□ □ (行1)
如果(i,0)是'#'，且(i-1,0)也是'#'，它们自然连通。
如果(i,0)不是'#'，需要放置一个检测器，花费+1。
从
dp[i-1][1]转移：
列i-1 列i
□ # (行0)
| |
# ---- □ (行1)
如果(i,0)是'#'，且(i-1,1)也是'#'，要与(i,0)连通，需要通过(i,1),当(i,1)不是'#'时，就需要放置一个检测器，故花费+(
s[i][1]== '#' ? 0 : 1)。如果(i,0)不是'#'，那么(i,0)需要放置一个检测器，花费+(
s[i][0]== '#' ? 0 : 1)。
状态转移方程如下：
如果
s[i][j]已经是'#'（已有检测器）：
dp[i][j] = min(dp[i-1][j], dp[i-1][1-j] + (s[i][1-j]=='#'?0:1))
如果
s[i][j]是'.'（需要放置检测器）：
dp[i][j] = min(dp[i-1][j], dp[i-1][1-j] + (s[i][1-j]=='#'?0:1)) + 1
边界条件
对于起始位置st（最左边有检测器的位置）：
如果
s[st][0]是'#'，则dp[st][0]=0如果
s[st][0]是'.'，则dp[st][0]=1（需要放置一个检测器）同理处理
dp[st][1]
如果起始位置两行都有检测器，需要确保它们连通，此时dp[st][0]=dp[st][1]=0。
最终结果
最终答案是min(dp[en][0], dp[en][1])，表示在最右边有检测器的位置en，使得所有检测器连通的最小花费。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+30;
char s[N][2];
int dp[N][2]; // dp[i][j]表示当前第i列第j行为'#'且与前面的检测器连通时的最小花费
void way(){
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);
}
}
//如果没有检测器直接输出0
if(st == n + 1){
cout<<0<<endl;
return;
}
// 初始化dp数组
memset(dp, 0x3f, sizeof(dp)); // 初始化为一个很大的值
// 处理起始位置
if(s[st][0]=='#') dp[st][0]=0; // 如果已经有检测器，花费为0
else dp[st][0]=1; // 否则需要放置一个检测器，花费为1
if(s[st][1]=='#') dp[st][1]=0; // 如果已经有检测器，花费为0
else dp[st][1]=1; // 否则需要放置一个检测器，花费为1
// 如果起始位置两行都有检测器，需要确保它们连通
if(s[st][0]=='#' && s[st][1]=='#') {
dp[st][0] = dp[st][1] = 0; // 两个位置都已有检测器，花费为0
}
for(int i=st+1;i<=en;i++){
// 计算dp[i][0]
if(s[i][0]=='#') { // 如果当前位置已有检测器
// 从上一列转移
dp[i][0] = min(dp[i-1][0], dp[i-1][1] + (s[i][1]=='#'?0:1));
} else { // 如果当前位置需要放置检测器
dp[i][0] = min(dp[i-1][0], dp[i-1][1] + (s[i][1]=='#'?0:1)) + 1;
}
// 计算dp[i][1]
if(s[i][1]=='#') { // 如果当前位置已有检测器
// 从上一列转移
dp[i][1] = min(dp[i-1][1], dp[i-1][0] + (s[i][0]=='#'?0:1));
} else { // 如果当前位置需要放置检测器
dp[i][1] = min(dp[i-1][1], dp[i-1][0] + (s[i][0]=='#'?0:1)) + 1;
}
}
cout<<min(dp[en][0],dp[en][1])<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
way();
return 0;
}示例分析
让我们以样例为例，详细分析算法的执行过程：
输入：
.##.....#
.#.#.#...
我们可以将其表示为一个2×9的矩阵（为了方便，列号从1开始）：
列号: 1 2 3 4 5 6 7 8 9
行0: . # # . . . . . #
行1: . # . # . # . . .
1. 确定计算范围
首先找到st=2（最左边有检测器的位置）和en=9（最右边有检测器的位置）。
2. 初始化dp数组
初始化dp数组为一个很大的值（表示无法到达的状态）。
对于起始位置st=2：
s[2] [0]='#'，所以dp[2] [0]=0（已有检测器，不需要额外花费）
s[2] [1]='#'，所以dp[2] [1]=0（已有检测器，不需要额外花费）
由于第2列的两行都有检测器，它们已经连通，所以dp[2] [0]=dp[2] [1]=0。
3. 逐列计算dp值
对于i=3（第3列）：
计算dp[3] [0]：
s[3] [0]='#'（已有检测器）
从dp[2] [0]转移：dp[2] [0]=0
从dp[2] [1]转移：dp[2] [1]=0，但需要通过(3,1)连接，s[3] [1]='.'，需要额外放置一个检测器，所以花费为0+1=1
取最小值：dp[3] [0]=min(0,1)=0
计算dp[3] [1]：
s[3] [1]='.'（需要放置检测器）
从dp[2] [1]转移：dp[2] [1]=0
从dp[2] [0]转移：dp[2] [0]=0，但需要通过(3,0)连接，s[3] [0]='#'，不需要额外放置检测器，所以花费为0+0=0
由于(3,1)需要放置检测器，额外花费1，所以dp[3] [1]=min(0,0)+1=1
对于i=4（第4列）：
计算dp[4] [0]：
s[4] [0]='.'（需要放置检测器）
从dp[3] [0]转移：dp[3] [0]=0
从dp[3] [1]转移：dp[3] [1]=1，但需要通过(4,1)连接，s[4] [1]='#'，不需要额外放置检测器，所以花费为1+0=1
由于(4,0)需要放置检测器，额外花费1，所以dp[4] [0]=min(0,1)+1=1
计算dp[4] [1]：
s[4] [1]='#'（已有检测器）
从dp[3] [1]转移：dp[3] [1]=1
从dp[3] [0]转移：dp[3] [0]=0，但需要通过(4,0)连接，s[4] [0]='.'，需要额外放置一个检测器，所以花费为0+1=1
取最小值：dp[4] [1]=min(1,1)=1
对于i=5（第5列）：
计算dp[5] [0]：
s[5] [0]='.'（需要放置检测器）
从dp[4] [0]转移：dp[4] [0]=1
从dp[4] [1]转移：dp[4] [1]=1，但需要通过(5,1)连接，s[5] [1]='.'，需要额外放置一个检测器，所以花费为1+1=2
由于(5,0)需要放置检测器，额外花费1，所以dp[5] [0]=min(1,2)+1=2
计算dp[5] [1]：
s[5] [1]='.'（需要放置检测器）
从dp[4] [1]转移：dp[4] [1]=1
从dp[4] [0]转移：dp[4] [0]=1，但需要通过(5,0)连接，s[5] [0]='.'，需要额外放置一个检测器，所以花费为1+1=2
由于(5,1)需要放置检测器，额外花费1，所以dp[5] [1]=min(1,2)+1=2
对于i=6（第6列）：
计算dp[6] [0]：
s[6] [0]='.'（需要放置检测器）
从dp[5] [0]转移：dp[5] [0]=2
从dp[5] [1]转移：dp[5] [1]=2，但需要通过(6,1)连接，s[6] [1]='#'，不需要额外放置检测器，所以花费为2+0=2
由于(6,0)需要放置检测器，额外花费1，所以dp[6] [0]=min(2,2)+1=3
计算dp[6] [1]：
s[6] [1]='#'（已有检测器）
从dp[5] [1]转移：dp[5] [1]=2
从dp[5] [0]转移：dp[5] [0]=2，但需要通过(6,0)连接，s[6] [0]='.'，需要额外放置一个检测器，所以花费为2+1=3
取最小值：dp[6] [1]=min(2,3)=2
对于i=7（第7列）：
计算dp[7] [0]：
s[7] [0]='.'（需要放置检测器）
从dp[6] [0]转移：dp[6] [0]=3
从dp[6] [1]转移：dp[6] [1]=2，但需要通过(7,1)连接，s[7] [1]='.'，需要额外放置一个检测器，所以花费为2+1=3
由于(7,0)需要放置检测器，额外花费1，所以dp[7] [0]=min(3,3)+1=4
计算dp[7] [1]：
s[7] [1]='.'（需要放置检测器）
从dp[6] [1]转移：dp[6] [1]=2
从dp[6] [0]转移：dp[6] [0]=3，但需要通过(7,0)连接，s[7] [0]='.'，需要额外放置一个检测器，所以花费为3+1=4
由于(7,1)需要放置检测器，额外花费1，所以dp[7] [1]=min(2,4)+1=3
对于i=8（第8列）：
计算dp[8] [0]：
s[8] [0]='.'（需要放置检测器）
从dp[7] [0]转移：dp[7] [0]=4
从dp[7] [1]转移：dp[7 ] [1]=3，但需要通过(8,1)连接，s[8] [1]='.'，需要额外放置一个检测器，所以花费为3+1=4
由于(8,0)需要放置检测器，额外花费1，所以dp[8] [0]=min(4,4)+1=5
计算dp[8] [1]：
s[8] [1]='.'（需要放置检测器）
从dp[7] [1]转移：dp[7] [1]=3
从dp[7] [0]转移：dp[7] [0]=4，但需要通过(8,0)连接，s[8] [0]='.'，需要额外放置一个检测器，所以花费为4+1=5
由于(8,1)需要放置检测器，额外花费1，所以dp[8] [1]=min(3,5)+1=4
对于i=9（第9列）：
计算dp[9] [0]：
s[9] [0]='#'（已有检测器）
从dp[8] [0]转移：dp[8] [0]=5
从dp[8] [1]转移：dp[8] [1]=4，但需要通过(9,1)连接，s[9] [1]='.'，需要额外放置一个检测器，所以花费为4+1=5
取最小值：dp[9] [0]=min(5,5)=5
计算dp[9] [1]：
s[9] [1]='.'（需要放置检测器）
从dp[8] [1]转移：dp[8] [1]=4
从dp[8] [0]转移：dp[8] [0]=5，但需要通过(9,0)连接，s[9] [0]='#'，不需要额外放置检测器，所以花费为5+0=5
由于(9,1)需要放置检测器，额外花费1，所以dp[9] [1]=min(4,5)+1=5
4. 计算最终结果
最终答案是min(dp[9] [0], dp[9] [1])=min(5, 5)=5，表示需要增加5个检测器使所有检测器连通。
可视化最终方案
一种可能的最终方案（'+'表示新增的检测器）：
列号: 1 2 3 4 5 6 7 8 9
行0: . # # + + . . . #
行1: . # . # . # + + .
或者：
列号: 1 2 3 4 5 6 7 8 9
行0: . # # . . . . + #
行1: . # + # + # + + .
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复