ABC450G 题解

本做法为随机化做法，思路是这篇题解
题目链接
记选的 \(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\)。
接下来我们维护以下信息

\[pre_{i,j}= \max\limits_{1\le k \le i \bigwedge g_k=j}a_k\]

\[suf_{i,j}= \max\limits_{i\le k \le n \bigwedge g_k=j}a_k\]

\[s_{i,j} = a_i+\sum_{k\in \left \{ 0,1,2,3 \right \} \bigwedge k \ne g_i \bigwedge k \ne j}suf_{i+1,k} \]

\[t_{i,j,k} = \max\limits_{i \le sufi \le n \bigwedge g_{sufi} = j} s_{sufi,k}\]
我们枚举第三个题目的位置 \(i\)，与第四个题目的类型 \(j\)。
那么此时的答案为

\[a_i + t_{i+1,j,g_i} + \sum_{k\in \left \{ 0,1,2,3 \right \} \bigwedge k \ne g_i \bigwedge k \ne j} pre_{i-1,k}\]
这样我们以 \(O(n)\) 的时间复杂度解决了问题。
接着我们随机赋值 \(600\) 次，那么错误率为 \((1-\frac{3}{256})^{600} \approx 8 \times 10^{-4}\)。可以接受。
实测 \(T = 300\) 时 WA 两个点， \(T = 500\) 时可以通过。
[code]#include#include#include#include#include#include#include#define mp make_pair#define fo(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 = rand() % 4;    fo(i , 1 , n) g = f[k];    //--------------------    fo(j , 0 , 3) pre[0][j] = -inf;    fo(i , 1 , n){        fo(j , 0 , 3){            pre[j] = pre[i - 1][j];            if(g == j) pre[j] = max(pre[j] , a);        }    }    //--------------------    fo(j , 0 , 3) suf[n + 1][j] = -inf;    go(i , n , 1){        fo(j , 0 , 3){            suf[j] = suf[i + 1][j];            if(g == j) suf[j] = max(suf[j] , a);        }    }    //--------------------    fo(i , 1 , n){        fo(j , 0 , 3){            s[j] = a;            fo(k , 0 , 3){                if(k == j or k == g) continue;                s[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[j][k] = t[i + 1][j][k];        int j = g;        fo(k , 0 , 3)            t[j][k] = max(t[j][k] , s[k]);    }    //--------------------    long long ans = -inf;    fo(i , 3 , n - 3){        fo(j , 0 , 3){            if(g == j) continue;            long long cur = t[i + 1][j][g] + a;            fo(k , 0 , 3){                if(k == g 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 >> a;    long long ans = -inf;    ans = solve();    fo(i , 1 , 300) ans = max(ans , solve());    if(ans < 0) cout