首先,如果 \(C_1==C_n\),那么最优的肯定是 \(A_1+A_n\)。
因为 \(A_1\) 和 \(A_n\) 无论如何都会被选到,不如只选他们两个。
其次,如果不满足 \(C_1=C_n\),对于所有的 \(i\)(\(1\le i < n\)),满足 \(C_1=C_i\) 且 \(C_{i+1}=C_n\),可以证明最优的答案一定存在于 \(A_1+A_i+A_{i+1}+A_n\) 中的最小值。
同上,选更多的数不如选更少的数,可以看一下这个样例。
1
4
1919
1110
最优的是花费 \(A_1+A_3\) 的能量清理 \(1\sim 3\) 块地板,在清理剩下的第 \(4\) 块地板。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;
int T,n,m,a[N],c[N];
signed main() {
cin>>T;
while(T--) {
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i) cin>>c[i];
int ans=1e18;
if(c[1]==c[n]) {
cout<<a[1]+a[n]<<'\n';
continue;
} for(int i=1;i<n;++i)
if(c[1]==c[i]&&c[i+1]==c[n])
ans=min(ans,(a[1]+a[i])
+(a[i+1]+a[n]));
cout<<ans<<'\n';
}// over
return 0;
}