AcWing 4214. 三元组-对不同的j分别枚举左i与右k
原题链接
困难
作者:
_T_
,
2022-01-22 21:12:59
,
所有人可见
,
阅读 331
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3005;
const int INF=2e9;//开两倍 因为left+right最大到2e9
int n,s[N],c[N];
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++) cin>>c[i];
int res=2e9;
for(int j=1;j<n-1;j++){
int left =2e9,right=2e9;//s[i]只与s[j]有关 s[k]只与s[j]有关 可以分别枚举
for(int i=0;i<=j-1;i++){
if(s[i]<s[j])
left=min(left,c[i]);
}
for(int k=j+1;k<n;k++){
if(s[k]>s[j])
right=min(right,c[k]);
}
if(left!=2e9&&right!=2e9) res=min(res,left+right+c[j]);
}
if(res==2e9) cout<<"-1";
else cout<<res;
return 0;
}