P9344 去年天气旧亭台 题解

tder · 2023-11-11 12:00:26 · 题解

\Large\color{black}\textbf{P9344 去年天气旧亭台} \Large\textbf{题解}

\textbf{题目传送门}

\textbf{更好的阅读体验}

贪心

显然的，当 c_1=c_n 时，直接使用一次操作清除 1\sim n 即可，代价 a_1+a_n，证明如下：若存在一种方案清除 1\sim k 和 (k+1)\sim n，使得其代价 (a_1+a_k)+(a_{k+1}+a_n)\le a_1+a_n，但又 a_k,a_{k+1}\ge1，得 a_1+a_n+1\le a_1+a_n，矛盾。

当 c_1\neq c_n 时，最优方案为消除 2 次，即我们需要找到一个 k，消除 1\sim k 和 (k+1)\sim n，那就是要 c_1=c_k 且 c_{k+1}=c_n，遍历所有满足条件的 k 取最小值即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 5, M = 1e10 + 5;
int t, n, a[N], c[N];
signed main() {
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        for(int i = 1; i <= n; i++) cin>>a[i];
        for(int i = 1; i <= n; i++) cin>>c[i];
        if(c[1] == c[n]) cout<<a[1] + a[n]<<endl;
        else {
            int ans = M;
            for(int k = 1; k < n; k++) 
                if(c[1] == c[k] && c[k + 1] == c[n])
                    ans = min(ans, a[1] + a[k] + a[k + 1] + a[n]);
            cout<<ans<<endl;
        }
    }
    return 0;
}