CF812B题解

康了康唯一的题解，说没必要用DP，我就给出DP的解法。

这其实是道水题，唯一的坑是有可能楼上没有开的灯，坑了我们机房的一堆人（ WA on test 4 ），剩下的就是DP。

我们用 a[n][0],表示第 n 层的第一个房间，用 a[n][1]，表示第 n 层的最后一个房间。

这里提供一个收集型的写法。

所以可得状态转移方程为 dp[i][j] = \min(dp[i + 1][!j] + m + 2, dp[i + 1][j] + a[i + 1][!j] \times 2 + 1) 对于 j,表示第 i 层的楼梯口，可以从下层（i+1 层）的另一边的楼梯口走来，也可以直接从同边走上来，最后取最小值。

最后附上代码。

 1 #include <iostream>
 2 using namespace std;
 3 const int Maxn = 20;
 4 int a[Maxn][2], dp[Maxn][2], n, m, s;
 5 char c;
 6 int main() {
 7   cin >> n >> m;
 8   for (int i = 1; i <= n; i++) {
 9     for (int j = 0; j <= m + 1; j++) {
10       cin >> c;
11       if (c == '1') {
12         a[i][0] = max(a[i][0], m + 1 - j), a[i][1] = max(a[i][1], j);//求出最左边和最右边
13       }
14     }
15   }
16   dp[n][1] = m + 1;//初始化（应为我们可以确定从初始点走到最右边是 $m+1$ 步）
17   for (int i = n - 1; i >= 1; i--) {
18     for (int j = 0; j <= 1; j++) {
19       dp[i][j] = min(dp[i + 1][!j] + m + 2, dp[i + 1][j] + a[i + 1][!j] * 2 + 1);//求值
20     }
21   }
22   for (s = 1; s < n && !a[s][0]; s++) {
23   }//过滤没灯的那几层
24   cout << min(dp[s][0] + a[s][1], dp[s][1] + a[s][0]);
25   return 0;
26 }