これはPASTボス問にしては易しめ?
https://atcoder.jp/contests/past202010-open/tasks/past202010_o
問題
N個の宝箱があり、いずれも施錠されている。
i個目の宝箱を開けるとA[i]円を得る。
M人の友人がおり、i番の友人にC[i]円払うと、宝箱L[i]~R[i]が開錠される。
得た金額-友人に払う金額の最大値を求めよ。
解法
SをAの累積和とする。
dp(n) := 先頭n個の宝箱のうち、得る金額-払う金額の最大値
dp2(n) := dp(n)+S(N)-S(n) とし、SegTreeで最大値を取れるようにする。
もし友人iによる開錠を試みる場合、dp(R[i]) = dp2(n)-(S(N)-S(R[i])) となるので、R[i]の小さい順にdp(R[i])を更新していこう。
int N,M; template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=-(1LL<<60); V comp(V l,V r){ return max(l,r);}; SegTree_1(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=comp(v,val[entry]); //上書きかチェック while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<ll,1<<18> st; vector<pair<int,int>> C[202020]; ll S[202020],dp[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) { cin>>x; S[i+1]=S[i]+x; dp[i+1]=-1LL<<60; } ll ret=0; dp[0]=0; st.update(0,S[N]); FOR(i,M) { int L,R,X; cin>>L>>R>>X; C[R].push_back({L-1,X}); } for(i=1;i<=N;i++) { dp[i]=dp[i-1]; FORR(c,C[i]) { int L=c.first; ll co=c.second; ll a=st.getval(L,i); a-=S[N]-S[i]; dp[i]=max(dp[i],a-co); } ret=max(ret,dp[i]); st.update(i,dp[i]+S[N]-S[i]); } cout<<ret<<endl; }
まとめ
割とすんなり解いてた。