Codeforces #536 Div2 E. Lunar New Year and Red Envelopes

ちょっと問題設定が強引だった気がするなぁ…。
http://codeforces.com/contest/1106/problem/E

問題

区間スケジューリングの問題である。
0～Nのタイムレンジにおいて、K個の仕事がある。
仕事iはS[i]～T[i]の間に従事開始することができ、いったん従事すると時刻D[i]まで他の仕事ができず、D[i]+1からまた別の仕事に取り掛かれるようになる。
また、その際得られる報酬はW[i]である。

なお、プレイヤーは仕事の順番を任意に選べず、以下のアルゴリズムで仕事を選ぶ。

• 従事できる仕事が何もないなら、その時間は何もしない。
• 従事できる仕事がある場合、W[i]が最大のものを選ぶ。W[i]がタイの場合、D[i]が最大の物を選ぶ。

ここで、プレイヤーの仕事の従事をM回(1回あたり時刻1だけ)止めることができるとき、プレイヤーの総報酬を最小化せよ。

解法

時刻において、プレイヤーが選ぶ仕事は一意に決まるので先にそれを求めてしまおう。
これは平面走査で(W[i],D[i])の最大値を毎時刻覚えていればよい。

あとは
dp(t,m) := 時刻tであとm回プレイヤーの仕事従事を止められるときの最小総報酬
とし、このテーブルを埋めていけばよい。
仕事を止めるか、(すでに求められた)仕事に従事するかの二択なのでこのDPはO(NM)で済む。

int N,M,K;

int S[101010],T[101010],D[101010],W[101010];

int to[101010],cost[101010];
vector<int> add[101010],del[101010];

ll dp[101010][202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	multiset<pair<int,int>> cand;
	cin>>N>>M>>K;
	
	FOR(i,K) {
		cin>>S[i]>>T[i]>>D[i]>>W[i];
		add[S[i]].push_back(i);
		del[T[i]].push_back(i);
	}
	
	FOR(i,N+2) FOR(j,M+1) dp[i][j]=1LL<<60;
	
	
	for(i=1;i<=N;i++) {
		FORR(a,add[i]) cand.insert({W[a],D[a]});
		if(cand.empty()) {
			to[i]=-1;
		}
		else {
			to[i]=cand.rbegin()->second+1;
			cost[i]=cand.rbegin()->first;
		}
		
		FORR(a,del[i]) cand.erase(cand.find({W[a],D[a]}));
	}
	
	dp[1][M]=0;
	for(i=1;i<=N;i++) {
		if(to[i]==-1) {
			FOR(j,M+1) dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
		else {
			FOR(j,M+1) {
				dp[to[i]][j]=min(dp[to[i]][j],dp[i][j]+cost[i]);
				if(j) dp[i+1][j-1]=min(dp[i+1][j-1],dp[i][j]);
			}
		}
	}
	
	
	ll ret=1LL<<60;
	FOR(i,M+1) ret=min(ret,dp[N+1][i]);
	cout<<ret<<endl;
	
	
}

まとめ

まぁこれはややこしいだけで難しくはないかもな。