Code Formula 2014 本選 : D - 映画の連続視聴

本選は出場したわけではないので練習のみ。
http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_d

問題

N回分の映画上映時間と映画の種類が与えられる。
同じ映画を連続してk個見ると、１回あたりH[k]の幸福度が得られる。
当然ながら時間帯が重複する映画を複数見ることはできない。

なお、映画は連続して見るほど１回あたりの幸福度が上昇する（H[k]＜H[k+1]である）。
最適な順番で映画を見ると、最大どれだけの幸福度が得られるか。

解法

映画の開始時間でソートし、順にDPしていく。
その際、簡単に考えると[映画番号][同じ種類を連続して見た回数]を状態とし、幸福度を最大化すればよいが、これだとO(N^3)かかりTLEする。

ここで以下の２つの考察を行う。

• 同じ映画を連続して見るほど幸福度が高いなら、ある映画番号において、[同じ種類を連続して見た回数]も幸福度も高い状態があるなら、それより[同じ種類を連続して見た回数]が低い状態はそれ以上チェックする必要がない。
• 今ある映画番号xにおける幸福度の最大化を行うとする。映画番号i＜jである２つの同じ種類の映画があるとき、後に開始されるjの方が必ず幸福度が高い。よって映画番号i番はチェックする必要がない。

これらにより探索対象を減らすことで高速化できる。
[同じ種類を連続して見た回数]をmapで管理したけど、これでO(N^2*logN)位かな？

int N;
int H[3001];
int M[3001],S[3001],E[3001];
int vis[3001];
pair<int,int> P[3001];
map<int,int> MM[3000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>H[i];
	FOR(i,N) cin>>M[i]>>S[i]>>E[i];
	FOR(i,N) P[i]=make_pair(S[i],i);
	sort(P,P+N);
	
	int ma=0;
	FOR(i,N) {
		x=P[i].second;
		map<int,int> TM;
		TM[-1]=H[0];
		ZERO(vis);
		for(j=i-1;j>=0;j--) if(E[P[j].second]<=S[x]) {
			if(vis[M[P[j].second]]) continue;
			vis[M[P[j].second]]=1;
			if(M[x]!=M[P[j].second]) {
				ITR(it,MM[j]) TM[-1]=max(TM[-1],it->second+H[0]);
			}
			else {
				ITR(it,MM[j]) TM[-it->first-1]=max(TM[-it->first-1],it->second+H[it->first]);
			}
		}
		int tma=0;
		ITR(it,TM) if(it->second>tma) MM[i][-it->first]=tma=it->second;
		ma=max(ma,tma);
	}
	cout << ma << endl;
}

まとめ

最初どうしようかと思ったけど、後者の考察に早めにたどり着けて良かった。
でもCから急に難易度上がったな。