一道某俱乐部测试题的题解

· · 算法·理论

这是一道你谷没有收录、网上也没有的题目的题解。

形式化题目大意

给定一个长度为 N 的正整数序列 A 及长度为 N 的正整数序列 B，你可以将 B 中所有元素任意插入至 A 中形成一个新的序列，然后再新序列中选择一些元素，要求选择的元素两两不相邻。求选择元素和的最大值。

数据保证 1\le N\le 3000,1\le M\le 100。

如果没有 B……

一个 trivial 的问题。令 dp_{i,0/1} 表示 A 中前 i 个数中，选（第二维为 1）或不选（第二维为 0）元素 i 的答案。有转移式：

dp_{i,0}=\max_{j\in \{0,1\}}\{dp_{i-1,j}\} dp_{i,1}=dp_{i-1,0}+A_i

答案为：

\max_{j\in \{0,1\}}\{dp_{N,j}\}

显然，时间复杂度为 \Theta(n)。

一种较为暴力的 DP

很轻易地想到一种状压 DP 的思路。令 dp_{i,S,0}(S\sube [1,M]) 表示最后考虑的 A 中元素为 A_i，并将所有 B_{S_i} 全部插入（顺序、位置任意），且最后一个元素选（第三维为 1）或不选（第三维为 0）的答案。注意，考虑的序列中最后一个元素不一定是 A_i。 有转移式：

dp_{i,S,0}=\max\left\{dp_{i-1,S,0},dp_{i-1,S,1},\max_{j\in S,k\in \{0,1\}}\left\{dp_{i,S/\{j\},k}\right\}\right\} dp_{i,S,1}=\max\left\{dp_{i-1,S,0}+A_i,\max_{j\in S}\left\{dp_{i,S/\{j\},0}+B_j\right\}\right\}

答案为：

\max_{k\in \{0,1\}}\{dp_{N,[1,M],k}\}

显然，时间复杂度是 \Omicron(NM2^M)，会超时。

优化思路

运用一下贪心的思想。我们尽可能的让 B 中大的元素产生贡献，对于无法产生贡献的位置用小的元素填充。令 dp_{i,j,k,l} 表示最后考虑的 A 中元素为 A_i，并让 B 中最大的 j 个元素产生贡献，且考虑了 B 中最小的 k 个元素不让它们产生贡献，最后一个元素选或不选（由第四维决定）的答案。有转移式：

dp_{i,j,k,0}=\max\left\{dp_{i-1,j,k,0},dp_{i-1,j,k,1},[k>0]dp_{i,j,k-1,0},[k>0]dp_{i,j,k-1,1}\right\} dp_{i,j,k,1}=\max\left\{dp_{i-1,j,k,0}+A_i,[j>0](dp_{i,j-1,k,0}+B'_j)\right\}

此处 B' 表示 B 从大到小排列所得的序列。

答案为：

\max\left\{dp\right\}

显然，时空复杂度均为 \Theta(NM^2)。

AC Code

#include <bits/stdc++.h>
#define dp(i, j, k, l) (j < 0 || k < 0 ? 0 : _dp[i][j][k][l]) // 防止出现下标小于0的情况
using namespace std;
using ll = long long;
using lll = __int128;
using ull= unsigned long long;
using vi = vector<int>;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f, N = 3e3, M = 100;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, m, a[N + 5], b[M + 5], _dp[N + 5][M + 5][M + 5][2], ans;

int tmax(int a, int b, int c){
    if(a >= b && a >= c) return a;
    else if(b >= a && b >= c) return b;
    else return c;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; ++ i) cin >> b[i];
    sort(b + 1, b + m + 1, greater<int>());
    for(int i = 1; i <= n; ++ i) for(int j = 0; j <= m; ++ j) for(int k = 0; k <= m - j; ++ k){
        _dp[i][j][k][0] = tmax(dp(i - 1, j, k, 0), dp(i - 1, j, k, 1), max(dp(i, j, k - 1, 0), dp(i, j, k - 1, 1)));
        _dp[i][j][k][1] = max(dp(i - 1, j, k, 0) + a[i], dp(i, j - 1, k, 0) + b[j]);
        ans = tmax(ans, dp(i, j, k, 0), dp(i, j, k, 1));
    }
    cout << ans;
}