本做法为随机化做法，思路是这篇题解
题目链接
记选的 \(6\) 个题目为 \(k_{1/2/3/4/5/6}\)。
首先我们将题目类型随机赋值为 \(0/1/2/3\)，显然原来不合法的方案在随机赋值之后仍然不合法，而实际上的最优解在现在仍然合法的概率为 $\frac{3}{256} $。
证明：
-
\(k_3\) 与 \(k_4\) 不相同的概率为 \(\frac{3}{4}\)，因为 \(k_3\) 可以随便取，之后 \(k_4\) 的值只能在 \(0/1/2/3\) 中挑除了 \(k_3\) 以外剩下的 \(3\) 个。
-
固定 \(k_3\) 与 \(k_4\) 之后，\(k_{1/2/3/4}\) 互不相同的概率为 \(\frac{1}{4} \times \frac{2}{4}=\frac{1}{8}\)，因为 \(k_1\) 可以挑 \(4\) 个中的 \(2\) 个，\(k_2\) 只能挑 \(4\) 个中的 \(1\) 个。
-
同理 \(k_{3/4/5/6}\) 互不相同的概率也为 \(\frac{1}{8}\)。总概率为 \(\frac{3}{4} \times \frac{1}{8}\times \frac{1}{8}=\frac{3}{256}\)。
这样我们就将题目类型数缩减到了 \(4\)。设随机赋值后新的题目类型为 \(g_i\)。
接下来我们维护以下信息
我们枚举第三个题目的位置 \(i\)，与第四个题目的类型 \(j\)。
那么此时的答案为
这样我们以 \(O(n)\) 的时间复杂度解决了问题。
接着我们随机赋值 \(600\) 次，那么错误率为 \((1-\frac{3}{256})^{600} \approx 8 \times 10^{-4}\)。可以接受。
实测 \(T = 300\) 时 WA 两个点， \(T = 500\) 时可以通过。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#define mp make_pair
#define fo(i , x , y) for(int i = x ; i <= y ; i++)
#define go(i , x , y) for(int i = x ; i >= y ; i--)
using namespace std;
mt19937 rd(time(0));
const int maxn = 100000;
const long long inf = 100000000000;
int n , k[maxn + 5];
long long a[maxn + 5] , f[maxn + 5] , g[maxn + 5];
long long pre[maxn + 5][4] , suf[maxn + 5][4] , s[maxn + 5][4] , t[maxn + 5][4][4];
long long solve(){fo(i , 1 , n) f[i] = rand() % 4;fo(i , 1 , n) g[i] = f[k[i]];//--------------------fo(j , 0 , 3) pre[0][j] = -inf;fo(i , 1 , n){fo(j , 0 , 3){pre[i][j] = pre[i - 1][j];if(g[i] == j) pre[i][j] = max(pre[i][j] , a[i]);}}//--------------------fo(j , 0 , 3) suf[n + 1][j] = -inf;go(i , n , 1){fo(j , 0 , 3){suf[i][j] = suf[i + 1][j];if(g[i] == j) suf[i][j] = max(suf[i][j] , a[i]);}}//--------------------fo(i , 1 , n){fo(j , 0 , 3){s[i][j] = a[i];fo(k , 0 , 3){if(k == j or k == g[i]) continue;s[i][j] += suf[i + 1][k];}}}//--------------------fo(j , 0 , 3)fo(k , 0 , 3)t[n + 1][j][k] = -inf;go(i , n , 1){fo(j , 0 , 3)fo(k , 0 , 3) t[i][j][k] = t[i + 1][j][k];int j = g[i];fo(k , 0 , 3)t[i][j][k] = max(t[i][j][k] , s[i][k]);}//--------------------long long ans = -inf;fo(i , 3 , n - 3){fo(j , 0 , 3){if(g[i] == j) continue;long long cur = t[i + 1][j][g[i]] + a[i];fo(k , 0 , 3){if(k == g[i] or k == j) continue;cur += pre[i - 1][k];}ans = max(ans , cur);}}return ans;
}
int main(){// ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0);// freopen(".in" , "r" , stdin);// freopen(".out" , "w" , stdout);cin >> n;fo(i , 1 , n) cin >> k[i] >> a[i];long long ans = -inf;ans = solve();fo(i , 1 , 300) ans = max(ans , solve());if(ans < 0) cout << "-1\n";else cout << ans << "\n";
}