题目链接
题目描述
有一个 $n$ 行 $m$ 列的网格，第 $i$ 行 $j$ 列上有数字 $a_{i,j}$ 。每个位置需要从上下左右四个方向中选择互相垂直的两个。
定义 $w(x)=x+popcnt(x)$ ，其中 $popcnt(x)$ 表示 x 的二进制位中 1 的位的数量。
如果两个相邻的位置 $(x1,y_1),(x_2,y_2)$ 互相位于对方选择的某个方向上，则对答案由 $w(a{x1,y_1}\ xor\ a{x_2,y_2})$ 的贡献，其中 $xor$ 表示二进制中的按位异或。
小 Z 想问你答案的最大值是多少。
输入描述:
第一行，输入 $n,m$ 。
接下来 $n$ 行 $m$ 列，输入这个网格。
输出描述:
输出答案的最大值。
示例1
输入
输出
动态规划~
因为选定的两个方向必须垂直，所以我们可以将竖直方向和水平方向分开计算，假设先计算水平方向的最大值，对某一行 $i$，用 $dp[j][0/1]$ 表示这一列的最大值，$0$ 表示选左边，$1$ 表示选右边，则有如下状态转移方程：
- $dp[j][0]=max(dp[j-1][0],dp[j-1][1]+w(a[i][j-1]\oplus a[i][j])$
- $dp[j][1]=max(dp[j-1][0],dp[j-1][1])$
每一行的最大值就是 $max(dp[m][0],dp[m][1])$，累加即可，对竖直方向同理，AC代码如下：
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
| #include <bits/stdc++.h>
using namespace std;
int n, m, ans, a[1005][1005], dp[1005][2];
int f(int x1, int y1, int x2, int y2) {
return (a[x1][y1] ^ a[x2][y2]) + __builtin_popcount(a[x1][y1] ^ a[x2][y2]);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= m; j++) {
dp[j][0] = max(dp[j - 1][0], dp[j - 1][1] + f(i, j - 1, i, j));
dp[j][1] = max(dp[j - 1][0], dp[j - 1][1]);
}
ans += max(dp[m][0], dp[m][1]);
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i++) {
for (int j = 2; j <= n; j++) {
dp[j][0] = max(dp[j - 1][0], dp[j - 1][1] + f(j - 1, i, j, i));
dp[j][1] = max(dp[j - 1][0], dp[j - 1][1]);
}
ans += max(dp[m][0], dp[m][1]);
}
cout << ans;
return 0;
}
|