読者です 読者をやめる 読者になる 読者になる

Time Table (AOJ2603)

今気づいたんだけど,問題名Time Tableなんだね,ずっとTiMe Tableだと思ってた(AOJ-ICPCの表記がそうなってる).
追記:asiさんのコメントの通り,TiMe Tableが正しいようです,AOJ側が間違ってるようだ.
さらに追記:square1001さんのコメントの通り,AOJの表記もTiMe Tableになおっていた.
まあ知識ゲーかなあ・・・(JOIの山岳救助隊とか)
この問題ではlogは定数です.

monotone minima
H*Wのmatrixで,行最小値のある場所(いっぱいあったら左(右でもいいけどどっちかで固定))が下に行くにつれて右に行く
ときmonotoneという
この時に全部の行の最小値の場所をO(NlogN)で求める
もちろん行列がもともとそのまま与えられてたらなんの意味もないけど,
得るのに計算量がかかる何らかの関数で与えられてたりしたら有用

Monge->totally monotone
で,この時頑張ればlogが取れる(SMAWK)んだけど,結構面倒

#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 A,N,K,o[2000],t[2000];
int w[2001][2001];
int inf=1e9;
int dp[2001][2001];

int mni[2000];
void minima(int d,int ia,int ib,int ja,int jb){	//[ia,ib]*[ja,jb]
	if(ia>ib) return;
	if(ia==ib){
		int mn=0,id=-1;
		for(int j=ja;j<=jb;j++){
			int tmp=dp[j][d]+w[j+1][ia];
			if(id<0||mn>tmp) id=j,mn=tmp;
		}
		mni[ia]=id;
		return;
	}
	int im=(ia+ib)/2;
	minima(d,im,im,ja,jb);
	minima(d,ia,im-1,ja,mni[im]);
	minima(d,im+1,ib,mni[im],jb);
}
int main(){
	rep(i,2001) rep(j,2001) dp[i][j]=inf;
	cin>>A>>N>>K;
	rep(i,A) cin>>o[i];
	rep(i,N){
		int x,y;
		cin>>x>>y;
		t[i]=x-o[y-1];
	}
	sort(t,t+N);
	rep(r,N){
		for(int l=r-1;l>=0;l--){
			w[l][r]=w[l+1][r]+t[r]-t[l];
		}
	}
	rep(i,N) dp[i][0]=w[0][i];
	rep1(d,K-1){
		minima(d-1,0,N-1,0,N-1);
		rep(i,N){
			int j=mni[i];
			dp[i][d]=dp[j][d-1]+w[j+1][i];
		}
	}
	cout<<dp[N-1][K-1]<<endl;
}