Link
2019的四川NOI题目，很经典的动态规划题目。
首先设$Dp[i][j][k][l]$表示当到达$(i,~j)$点的时候恰好用了$k$次粉刷的机会，其中$l$只有$0$和$1$两种取值，因为题目中说的一个格子如果没有被粉刷或者粉刷上了错误的颜色都算粉刷错误，因此我们可以将这两种情况分开来看，统一成$0$，如果粉刷对了就是$1$。
状态转移：
对于每一次换木板的时候要刷一次，那么最优情况下，也就是跟前一个木板完全一样的情况下，我们将上一块木板的$Dp$转移过来就可以了。记住要把$1$和$0$的状态都转移过来。
然后对于上一个格子和当前格子的颜色都一样的话，我们就像换行一样进行处理。将上一个格子的状态直接转移过来就可以了。
如果上一个格子的颜色与当前格子的颜色不一样，那么可以选择
- 继续上一个格子的颜色，不减少机会，但是当前的格子就错误了。
- 减少一次机会，换一个k，当前的格子粉刷正确。所以从思路上来说是非常简单的，只要你能想到是几维的Dp，接下来的转移方程基本是水到渠成的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std ;
typedef long long LL ;
const int MAXN = 60 ;
const int MAXM = 60 ;
const int MAXT = 2510 ;
int N, M, K, Color[MAXN][MAXM], Dp[MAXN][MAXM][MAXT][2], Ans ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
int main() {
N = Read(), M = Read(), K = Read() ;
for (int i = 1 ; i <= N ; i ++) {
string A ; cin >> A ;
for (int j = 1 ; j <= M ; j ++)
Color[i][j] = A[j - 1] - '0' ;
}
for (int i = 1 ; i <= N ; i ++)
for (int j = 1 ; j <= M ; j ++)
for (int k = 1 ; k <= K ; k ++) {
if (j == 1) Dp[i][j][k][0] = max(Dp[i - 1][M][k - 1][0], Dp[i - 1][M][k - 1][1]),
Dp[i][j][k][1] = max(Dp[i - 1][M][k - 1][0], Dp[i - 1][M][k - 1][1]) + 1 ;
else
if (Color[i][j] == Color[i][j - 1])
Dp[i][j][k][1] = Dp[i][j - 1][k][1] + 1,
Dp[i][j][k][0] = Dp[i][j - 1][k][0] ;
else {
Dp[i][j][k][1] = max(Dp[i][j - 1][k - 1][1] + 1, Dp[i][j - 1][k][0] + 1) ;
Dp[i][j][k][0] = max(Dp[i][j - 1][k][1], Dp[i][j - 1][k - 1][0]) ;
}
Ans = max(Ans, max(Dp[i][j][k][0], Dp[i][j][k][1])) ;
} printf("%d", Ans) ; return 0;
}
后记
没有写滚动数组，追求完美的当然可以滚动，但是不滚动数组也依然能过啦~。