Good Bye 2014 : C. New Year Book Reading

こういう問題設定は好き。
http://codeforces.com/contest/500/problem/C

問題

1～Nの番号が振られたN冊の本があり、それぞれの重さはW[i]である。
この本は１つの山に積まれている。

この本の山に対し、M日間読書を行う。
i日目にはB[i]の番号の本を読む。
その際、山の中からB[i]の番号の本を抜き出し、読み終わったら山の上に積む。

山の中の本を抜き出すには、その上に積まれた本の総重量分の労力がかかる。
初期状態では本を任意の順に積むことが出来るとするとき、M日間の合計の労力の最小値を求めよ。

解法

読む本はできるだけ山の上に置いておくと良いのは明らか。
よって以下のように本が登場する順に上に置かれるよう処理していくと良い。
初期状態で山は空とする。

• i日目の本B[i]が過去既出→山の上に移動して、上に積まれた本の重量分労力を加算。
• i日目の本B[i]が未出→今まで山の一番したにあったと仮定し、山の上に追加して、上に積まれた本の重量分労力を加算。

int N,M;
int W[1020];
int B[1020];
int st[1020];
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>W[i];
	ll ret=0;
	FOR(i,M) {
		cin>>B[i];
		B[i]--;
		if(st[B[i]]==0) st[B[i]]=1, V.push_back(B[i]);
		FOR(x,V.size()) {
			if(V[x]!=B[i]) ret += W[V[x]];
			else break;
		}
		for(y=x;y>=1;y--) V[y]=V[y-1];
		V[0]=B[i];
	}
	cout<<ret<<endl;
}

まとめ

制限が小さいので方針さえわかれば実装はすぐ。
方針を定めるまでにちょっと思考が必要な問題。