EDPC Q-flowers

概要

N本の花が一列に並んでいて、各花には高さhと美しさaがあります。花の高さはすべて異なります。ここから花を抜き去って残った花の高さが単調増加になるようにしたとき、残った花の美しさの総和の最大値を求めてください。

考え方

1.SegmentTree解法

・美しさaがすべて1である場合

→高さが単調増加するようになるべく多く花を取る問題になる。これはLISにほかならない
これは、次のようなDPを保持した動的計画法で求められる
DP[i]=残った花の高さのMAXがiであるときの、残った花の数
遷移：i=1...nについて、以下を行う。DP[0],DP[1]...DP[h[i]-1]の区間maxを取得し、それに1を加えたものをDP[h[i]]に代入する
解答：max(DP[1],...DP[N])
//区間maxはSegmentTreeで取得できるので、この問題を解くことができる。

・美しさaが異なる場合(重み付きLIS)

DPを以下のように変更する
DP[i]=残った高さのMAXがiであるときの、残った花の美しさの総和
遷移：i=1...nについて、以下を行う。DP[0],DP[1]...DP[h[i]-1]の区間maxを取得し、それにa[i]を加えたものをDP[h[i]]に代入する
解答：max(DP[1],...DP[N])

具体例

例題1

コード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;

typedef  long long ll;

ll op(ll a,ll b){
  return max(a,b);
}
ll e(){
  return 0;
}

int main(){
  int n;
  cin>>n;
  vector<int>h(n),a(n);
  segtree<ll,op,e>seg(n+1);
  for(int i=0;i<n;i++)cin>>h[i];
  for(int i=0;i<n;i++)cin>>a[i];

  for(int i=0;i<n;i++){
    ll intervalMax=seg.prod(0,h[i]);
    seg.set(h[i],intervalMax+a[i]);
  }
  ll ans=seg.all_prod();
  cout<<ans<<endl;
  }