ARC196 A. Adjacent Delete
Difficulty:None
問題
長さ$ Nの数列が与えられる。隣接する要素を取り除いて差の絶対値をスコアとして得る。スコアの最大値を求めよ。
解法
偶奇が異なるもの同士でしかマッチングできないが、Nが偶数のとき、偶奇さえ異なれば任意のマッチングを作ることができる。これは括弧列を考えるとわかる。
Nが奇数の時は最後に残る要素を固定し、左右からDPの結果を持っておいてそれの和の最大値みたいな感じにすればよい。関数化すると実装が楽。
DP（というか結果をメモしておくだけだが）は、大きい要素と小さい要素に分けておいてそれぞれの和を保持しておき、中央値との差分をとればよい。pqなどを使って（昇順のpqと降順のpqを用意）やってもといし、WaveletMatrixの強めのものを使うことでも解けるとか。
実装
code:cpp
bool solve(){
LL(n);
vector<ll>a(n);cin >> a;
auto f = &(vector<ll>&A,vector<ll>&dp){ {
priority_queue<ll>l;
pqg<ll>r;
ll lsum{},rsum{};
rep(i,1,n,2){
while(l.size()>(i+1)/2){
ll tmp = l.top();l.pop();
lsum -= tmp;
rsum += tmp;
r.push(tmp);
}
while(r.top()<l.top()){
lsum -= l.top()-r.top();
rsum -= r.top()-l.top();
l.push(r.top());
r.push(l.top());
l.pop();r.pop();
}
dpi = (l.top()*((i+1)/2) - lsum) + (rsum-l.top()*((i+1)/2)); }
}
};
vector<ll>dp1(n),dp2(n);
f(a,dp1);
reverse(ALL(a));
f(a,dp2);
reverse(ALL(dp2));
if(n%2==0){
O(dp1.back());
}
else{
rep(i,2,n-1,2){
}
O(ans);
}
deb(dp1);
deb(dp2);
return true;
}