如果我们将金字塔翻转 \(3\) 次，会变为原金字塔。所以，翻转 \(n\) 次，相当于翻转 \(n\bmod 3\) 次，为了使用魔法值更小，所以翻转的次数一定 \(<3\)。
因此，我们讨论不翻转和翻转 \(1\) 或 \(2\) 次金字塔三种情况，从中取出最优的即可。
现在思考如何如何最优化调换操作。
结论：合法路径所经过的最大和一定是每行最大值之和。
证明：这还是比较显然地，我们设任意一条合法路径为 \(A_{1,b_1},A_{2,b_2},\cdots,A_{n,b_n}\)，设第 \(i\) 行的最大值在第 \(mx_i\) 列。那么，交换 \(A_{1,b_1},A_{1,mx_1},A_{2,b_2},A_{2,mx_2},\cdots ,A_{n,b_n},A_{n,mx_n}\)，那么 \(A_{1,mx_1},A_{2,mx_2},\cdots ,A_{n,mx_n}\) 这些每一行的最大值就在一条合法路径上了！
我们发现，如果一条合法路径上有一点 \(A_{i,j}\)，它同时是 \(A_{i,mx_i}\)，那么这一行就不需要进行调换操作了！
因此，我们要找到一条合法路径让他所包含的最大值最多。如何做到呢？类似于数字金字塔了，不懂同学们可以去学习一下这题。
\(f[x][y]\) 表示从金字塔最后一行到 \((x,y)\) 最多会经过几个最大值，\(Max[i][j]\) 表示第 \(i\) 行的 \(j\) 元素是否为最大值。
那么有 DP 方程：\(f[x][y]=Max[x][A[x][y]]+\max(f[x+1][y],f[x+1][y+1])\)。
那么 \(f[1][1]\) 就是一条合法路径所包含的最大值数量最多是多少。那么需要调换的次数就是 \(n-f[1][1]\)。
总代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int A[MAXN][MAXN], f[MAXN][MAXN], Max[MAXN][MAXN], n, M_num, M_sum, B[MAXN][MAXN];
int MSUM;
void S_max() {
memset(Max, 0, sizeof(Max));
MSUM = 0;
for (int i = 1; i <= n; i++) {
int Max2 = 0;
for (int j = 1; j <= i; j++) {
Max2 = max(Max2, A[i][j]);
}
Max[i][Max2] = 1;
MSUM += Max2;
}
}
void fz() {
int num1 = 0, num2 = 0;
for (int i = n; i >= 1; i--) {
num2 = 1;
num1++;
int w = i;
for (int j = n; j >= i; j--) {
B[num1][num2++] = A[j][n - w + 1];
w++;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
A[i][j] = B[i][j];
}
}
memset(f, -1, sizeof(f));
memset(Max, 0, sizeof(Max));
MSUM = 0;
S_max();
}
int search(int x, int y) {
if (f[x][y] == -1) {
if (x == n) f[x][y] = Max[x][A[x][y]];
else f[x][y] = Max[x][A[x][y]] + max(search(x + 1, y), search(x + 1, y + 1));
}
return f[x][y];
}
void gx(int mm) {
if (MSUM > M_sum) {
M_sum = MSUM;
M_num = (n - f[1][1]) + mm;
}
else if (MSUM == M_sum) {
M_num = min(M_num, (n - f[1][1]) + mm);
}
}
int main() {
cin >> n;
memset(f, -1, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> A[i][j];
}
}
S_max();
search(1, 1);
gx(0);
fz();
search(1, 1);
gx(n);
fz();
search(1, 1);
gx(2 * n);
cout << M_sum << " " << M_num << endl;
}