《E - Don't Isolate Elements》

dp

 刚开始拿到这道题时，我总是在想：第一行翻不翻转对下面情况的影响，在什么情况下要反转，等一系列情况

最后我发现：这些情况不如我可以利用状态转移来实现，于是我朝着dp方向想。

一开始我设置的dp是dp[i][j]:在第i-1行即以上行都合法，而且使第i行也合法同时第i行翻不翻转的状态为j的最小操作次数

但是这样设置我下面就面临了问题：

　　1.第i行的合法性与第i-1行和第i+1行是相关的，

　　2.既然第i行的合法性与第i+1行是相关的，我又如何能够保证在第i+1还没被算出来之前，第i行是能够提前被算出来的呢？

　　即我状态转移不知道写。

　　3.我如何确定合法性？

解决:

　　dp[i]...：首先这里我便要重新定义：既然要知道第i+1行的状态才能知道第i行合法性，那便i表示保证第i-1以及以上行的合法性

，但是不保证第i行的合法性。

　　在状态转移的过程中，比如从第i-1行转移到第i行该如何转移？

　　因为dp[i-1]...不保证第i-1行合法性，我必须枚举第i行的状态和第i-1行的状态，以及要知道第i-2行的状态才能知道，第i-1行到底合不合法

于是：

　　dp[i][j][k]:表示保证第i-1以及以上行的合法性,并且第i-1行的状态为j,第i行的状态为k的最小操作次数

如果第i-1行在第i-2行状态为u,第i-1行状态为j,第i行状态为k的情况下，是合法的，那么进行状态转移：

k只有0,1两个状态

dp[i][j][k]=min(dp[i][j][k],dp[i-1][u][j]+k)

如何判断是否合法看check（）函数

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int INF = 0x3f3f3f3f;
 6 const int N = 1005;
 7 // dp[i][j][k]:表示在第i行,确保第i-1行即以上的行都是合法的情况下
 8 // 到达第i行状态是k,第i-1行状态是j的情况的最小操作数；
 9 int dp[N][2][2], n, m;
10 int a[N][N];
11 // 在第i-2行状态为u,第i-1行状态为j,第i行状态为k的情况下，第i-1行是否合法
12 bool check(int u, int j, int k, int h)
13 {
14     for (int i = 1; i <= m; i++)
15     {
16         int ns = j ? !a[h][i] : a[h][i];
17         int os;
18         if (h - 1 >= 1)
19         {
20             os = u ? !a[h - 1][i] : a[h - 1][i];
21             if (ns == os)
22                 continue;
23         }
24         if (i + 1 <= m)
25         {
26             os = j ? !a[h][i + 1] : a[h][i + 1];
27             if (ns == os)
28                 continue;
29         }
30         if (h + 1 <= n)
31         {
32             os = k ? !a[h + 1][i] : a[h + 1][i];
33             if (ns == os)
34                 continue;
35         }
36         if (i - 1 >= 1)
37         {
38             os = j ? !a[h][i - 1] : a[h][i - 1];
39             if (ns == os)
40                 continue;
41         }
42         return false;
43     }
44     return true;
45 }
46 int main()
47 {
48     cin >> n >> m;
49     for (int i = 1; i <= n; i++)
50         for (int j = 1; j <= m; j++)
51             scanf("%d", &a[i][j]);
52     memset(dp, 0x3f, sizeof(dp));
53     dp[1][0][0] = 0;
54     dp[1][1][0] = 0;
55     dp[1][0][1] = 1;
56     dp[1][1][1] = 1;
57     // 0代表不反转，1代表反转
58     for (int i = 2; i <= n; i++)
59         // 第i-1行状态：
60         for (int j = 0; j <= 1; j++)
61             // 第i-2行状态:
62             for (int u = 0; u <= 1; u++)
63                 // 第i行状态:
64                 for (int k = 0; k <= 1; k++)
65                 {
66                     if (check(u, j, k, i - 1))
67                         dp[i][j][k] = min(dp[i][j][k], dp[i - 1][u][j] + k);
68                 }
69     int ans = INF;
70     for (int i = 0; i <= 1; i++)
71         for (int j = 0; j <= 1; j++)
72             for (int k = 0; k <= 1; k++)
73             {
74                 if (check(i, j, k, n))
75                     ans = min(ans, dp[n][i][j]);
76             }
77     if (ans >= INF)
78         cout << -1;
79     else
80         cout << ans;
81     return 0;
82 }