Water Tank (AOJ1133)

えっと、でんじろう先生の方のWater Tankです.
これクソむずいと思う・・・ 実装方針を評価して個人的には700点くらい(もちろん実装強い人は何やっても解けるんだけど,うまい方針がある)

とりあえず計算量はどうでもいいのでtごとに毎回計算します.
h[i]:左からi個目の区間の高さ を更新していきます
まず蛇口ごとに独立にやってもいい(つまり時間というのはどうでもよくて順次h[i]を更新していければよい)ことがわかる.
pour(int x,double& v,int l,int r)という関数を考えます.こいつは何をやるかというと,まずこの図をご覧ください.

この図で上からトップダウンに呼んでいく.再帰内で計算する順はこの図に書いてある番号順.
左からx個目の区間(場所x)に注ぐんだけど,[l,r)に注ぎきれる(つまりlとrのとこの仕切りの高さのmin(uとする)まで全部うまる)か? そうなら[l,r)の間のhを全部uに設定する.
再帰(区間分割)をどう選ぶかというと,その区間の中で一番高い仕切りを選んでやる.これがかなり重要で,こうすることで呼ばれる区間は全部,"内側の仕切りより外側の仕切りのほうが高い"を満たす.こうすると上述のようなものが定義できる.この時実際の注ぎ口xがどっちの区間に近いか,で先にどっちを呼ぶか変わる.
注意だが,xは[l,r)に含まれているとは限らない!!例えば上の図では[0,2) (番号8に対応)をやるときx=2はこれに含まれていない,そして6,7の再帰のどっちが先かはxに近い方かどうかで判定されている.

まあつまり,蛇口から出る水が埋まる場所は図の番号の小さい順なので,その順に高さhを更新していくわけです.
この解法のどこがすごいかというと,ボトムアップじゃなくてトップダウンでやることで,どうしてもこの問題見た時に,時系列順に,なんか変なことが起こるまで注いでマージしたりする みたいな解法を思いつきがちだと思うんですけど,落ち着いて上の図を見るとああトップダウンのほうが見通しがいいなあ、となる
まあ何が言いたいかというと再帰DPが書けない人はダメ という話.僕はかけません.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,M,L;
double B[11],H[11],h[10];
int F[9];
double X[9];
void pour(int x,double& v,int l,int r){
	if(r-l>=2){
		int mx=l+1;
		for(int i=l+1;i<r;i++) if(H[i]>H[mx]) mx=i;
		if(x<mx){
			pour(x,v,l,mx);
			pour(x,v,mx,r);
		}else{
			pour(x,v,mx,r);
			pour(x,v,l,mx);
		}
	}
	double w=B[r]-B[l],u=min(H[l],H[r]);
	double dh=v/w;
	if(h[l]+dh<u){
		v=0;
		for(int i=l;i<r;i++) h[i]+=dh;
	}else{
		v-=(u-h[l])*w;
		for(int i=l;i<r;i++) h[i]=u;
	}
}
int main(){
	int Q;
	cin>>Q;
	rep(tt,Q){
		cin>>N;
		rep1(i,N) cin>>B[i]>>H[i];
		N++;
		B[0]=0,B[N]=100;
		H[0]=H[N]=50;
		cin>>M;
		rep(i,M){
			cin>>F[i]>>X[i];
			X[i]/=30;
			F[i]=lower_bound(B,B+N,F[i])-B-1;
		}
		cin>>L;
		rep(i,L){
			rep(j,N) h[j]=0;
			int p,t;
			cin>>p>>t;
			rep(j,M){
				double v=X[j]*t;
				pour(F[j],v,0,N);
			}
			p=lower_bound(B,B+N,p)-B-1;
			printf("%.8f\n",h[p]);
		}
	}
}