[Kickstart Round C 2019 B. Circuit Board] 动态规划

1. 题目链接

Kickstart Round C 2019 B. Circuit Board

2. 题目描述

3. 解题思路

$dp_{(i,j,k)}$ 表示右下角坐标为 $(i,j)$，高度为 $k$ 的子矩阵的最大宽度。假设下标从 $1$ 开始，那么有:

$$\begin{align}
dp_{(i,j,k)}=\min \lbrace dp_{(i,j,1)}, dp_{(i-1,j,k-1)}\rbrace, \quad \text{for any }i,k > 1.
\end{align}$$

因此， $ans=\max\lbrace dp_{(i,j,k)}*k\rbrace$

4. 参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
int T, R, C, K, V[MAXN][MAXN], ans;
int dp[2][MAXN][MAXN];

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-2.txt", "r", stdin);
#endif
    cin >> T;
    for(int cas = 1; cas <= T; ++cas) {
        cin >> R >> C >> K;
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= R; ++i) {
            for(int j = 1; j <= C; ++j) {
                cin >> V[i][j];
            }
        }
        ans = R;
        for(int i = 1; i <= R; ++i) {
            for(int j = 1; j <= C; ++j) {
                int maxv = V[i][j];
                int minv = V[i][j];
              	int f = i & 1;
              	dp[f][j][1] = 1;
                for(int k = 2; k <= j; ++k) {
                    minv = min(minv, V[i][j-k+1]);
                    maxv = max(maxv, V[i][j-k+1]);
                    if(maxv - minv > K) break;
                    dp[f][j][1] = k;
                }
                ans = max(ans, dp[f][j][1]);
                for(int k = 2; k <= i; ++k) {
                    dp[f][j][k] = min(dp[f][j][1], dp[f^1][j][k - 1]);
                    ans = max(ans, dp[f][j][k] * k);
                }
            }
        }
        printf("Case #%d: %d\n", cas, ans);
    }
    return 0;
}