Codeforces #186 Div2. D. Ilya and Roads

簡単なCに比べるとだいぶ難易度が上がるD。
http://codeforces.com/contest/313/problem/D

問題

1～Nまでの穴が並んでいる。
穴を直す業者がM個あり、それぞれL[i]～R[i]番までの穴をコストC[i]で修理してくれる。
N個中K個以上穴を直す最小コストを答えよ。

解法

XからYまでを直す最小コストを先に求める。
次に、「Xまでの穴のうちZ個直した」という状態を持ってDPしていけばよい。
N<=300なので、O(N^3)のDPで間に合う。

ll N,M,K;
ll P[302][302];
ll dp[302][302];

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>N>>M>>K;
	
	FOR(x,302) FOR(y,302) P[x][y]=1LL<<50;
	
	FOR(i,M) {
		cin>>x>>y>>f;
		P[x][y]=min(P[x][y],(ll)f);
	}
	
	FOR(i,301) {
		FOR(x,301) for(y=x;y<=300;y++) {
			if(x>0) P[x][y]=min(P[x][y],P[x-1][y]);
			P[x][y]=min(P[x][y],P[x][y+1]);
		}
	}
	
	FOR(x,N+1) {
		FOR(y,N+1) dp[x][y]=1LL<<50;
		dp[x][0]=0;
	}
	
	for(x=1;x<=N;x++) {
		FOR(y,x) dp[x][y]=dp[x-1][y];
		FOR(y,x) for(z=0;z<=x;z++) {
			dp[x][z+(x-y)]=min(dp[x][z+(x-y)], dp[y][z]+P[y+1][x]);
		}
	}
	
	ll res=1LL<<50;
	for(x=K;x<=N;x++) res=min(res,dp[N][x]);
	if(res>=1LL<<50) res=-1;
	cout << res << endl;
	
	return;
}

まとめ

珍しくオーソドックスなDP問題。