CF1736E Swap and Take
设在第 \(i\) 次操作后产生贡献的值为初始序列的 \(a_{p_i}\)，可以发现产生的贡献的指针移动方式为每次向后移动 \(1\)，而通过交换数字最多可以使得某个数字每次向后移动 \(1\)，由此可以得出每次产生贡献的位置单调不减，即 \(p_1 \le p_2 \le \cdots \le p_n\)。
这样若某次操作后的贡献点位置为 \(k_0\)，那么对于这之后的所有操作的贡献点 \(k\)，均有 \(k_0 \le k\)，而在最优策略下，若 \(k_0\) 产生贡献一定不会影响到 \(k_0\) 之后的位置，因此决策不具有后效性，可以进行 \(\tt{DP}\)。
设 \(f_{i, j, k}\) 表示在进行了 \(j\) 次操作后 \(a_k\) 在第 \(i\) 个位置产生了贡献的情况下最大的分数值，转移考虑 \(p_i\) 与 \(p_{i - 1}\) 之间的关系
- 若 \(p_{i - 1} = p_i\)，那么有 \(f_{i, j, k} \leftarrow f_{i - 1, j - 1, k} + a_k\)
- 若 \(p_{i - 1} \le p_i\)，通过枚举 \(p_{i - 1}\) 的值可以实现转移，有 $$f_{i, j, k} = \max\limits_{1 \le k^{\prime} < k} f_{i - 1, j - \left(k - i\right), k^{\prime}} + a_k$$，通过前缀最大值优化即可实现 \(\mathcal{O}(1)\) 转移。
总复杂度 \(\mathcal{O}(N^3)\)，可以通过。
Code
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
constexpr valueType MIN = std::numeric_limits<valueType>::min() >> 1;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
ValueVector A(N + 1);
for (valueType i = 1; i <= N; ++i)
std::cin >> A[i];
ValueCube F(N + 1, ValueMatrix(N + 1, ValueVector(N + 1, MIN))), G(N + 1, ValueMatrix(N + 1, ValueVector(N + 1, MIN)));
G[0][0][0] = F[0][0][0] = F[0][0][1] =0;
for (valueType k = 1; k <= N; ++k)
G[0][0][k] = std::max(G[0][0][k - 1], F[0][0][k]);
for (valueType i = 1; i <= N; ++i) {
for (valueType j = 0; j <= i; ++j) {
for (valueType k = 1; k <= N; ++k) {
if (j > 0)
F[i][j][k] = std::max(F[i][j][k], F[i - 1][j - 1][k] + A[k]);
if (j >= k - i && k >= i)
F[i][j][k] = std::max(F[i][j][k], G[i - 1][j - (k - i)][k - 1] + A[k]);
G[i][j][k] = std::max(G[i][j][k - 1], F[i][j][k]);
}
}
}
valueType ans = MIN;
for (valueType j = 0; j <= N; ++j)
for (valueType k = 1; k <= N; ++k)
ans = std::max(ans, F[N][j][k]);
std::cout << ans << std::endl;
}