[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$ 开始,那么有:

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

4. 参考代码

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
44
#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;
}
坚持原创技术分享,您的支持将鼓励我继续创作!