なぜDiv2 only回で3500ptとか出るんだ…。
https://codeforces.com/contest/1131/problem/G
問題
M個のドミノが左右一列に、互いに間隔1に並んで立っている。
それぞれのドミノiに対し、高さH[i]とコストC[i]が与えられる。
ドミノを1つ選択し、左右どちらかに倒すことを考える。
倒れた方向にある距離が高さ未満のドミノは同じ方向に倒れる。またこの動作は連鎖的に発生する。
ただしこの時、最初に倒したドミノの分のコストがかかる。
全ドミノを倒す最小コストを求めよ。
解法
Mが10^7と大きいので、O(M)解法を考える。
まず、各ドミノiを左右に倒した場合どこまで倒れるかL[i],R[i]をそれぞれ求めよう。
これはdequeを用いて求めることができる。
f(m) := 先頭からm番目までのドミノを倒すコスト
とする。f(m)は当然単調増加である。
m番目を左に倒す場合と、右に倒す場合を考え、最小値を取ろう。
- 左に倒す場合、L[m]まで倒れるのでf(m) = f(L[m]-1) + C[m]
- 直接または間接的に右に倒す場合、R[k]≧mであるようなkに対しf(m) = f(k-1)+C[k]
前者は1つしか値が無いが、後者がkの候補がいくつかある。
そこでdequeを使い{R[k],f(k-1)+C[k]}の∈をスライド最小値の要領で更新していこう。
int N,M; vector<int> A[303030],CT[303030]; int Q; int H[10101010]; ll C[10101010]; ll dp[10101010]; int L[10101010],R[10101010]; void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&M); FOR(i,N) { scanf("%d",&x); A[i].resize(x); CT[i].resize(x); FOR(j,x) scanf("%d",&A[i][j]); FOR(j,x) scanf("%d",&CT[i][j]); } scanf("%d",&Q); int cur=1; FOR(i,Q) { scanf("%d%d",&x,&y); FOR(j,A[x-1].size()) { dp[cur]=1LL<<60; H[cur]=A[x-1][j]; C[cur]=CT[x-1][j]*1LL*y; cur++; } } deque<pair<int,int>> D; for(i=1;i<=M;i++) { int LM=i-(H[i]-1); while(D.size() && D.back().second>=LM) LM=min(LM,D.back().first), D.pop_back(); L[i]=max(1,LM); D.push_back({L[i],i}); } D.clear(); for(i=M;i>=1;i--) { int RM=i+H[i]-1; while(D.size() && D.back().second<=RM) RM=max(RM,D.back().first), D.pop_back(); R[i]=min(M,RM); D.push_back({R[i],i}); } deque<pair<int,ll>> Q; for(i=1;i<=M;i++) { dp[i]=dp[L[i]-1]+C[i]; while(Q.size()&&Q.back().first<i) Q.pop_back(); if(Q.size()) dp[i]=min(dp[i],Q.back().second); ll co=dp[i-1]+C[i]; if(Q.empty()||co<Q.back().second) Q.push_back({R[i],co}); } cout<<dp[M]<<endl; }
まとめ
O(M)にさせたいとはいえ、変わった入力方式。