Codeforces #600 Div2 E. Antenna Coverage

また4か月以上ため込んでる…。
https://codeforces.com/contest/1253/problem/E

問題

1次元の空間で、いくつかの区間が与えられる。各区間は、中心の座標とそこからの半径で表現される。
コストを1払うと、いずれかの空間の半径を1増やせる。
[1,M]の区間を最低1つの区間で覆うのに必要な最小コストを求めよ。

解法

区間を座標昇順にソートしておく。
f(i,x) := i番目までの区間で[1,x]を覆う最小コスト
とする。これは明らかにxに対して単調増加である。

i+1番目の中心をa,半径をrとすると、追加コストを払わない場合f(i+1,a+r)=min(f(i,a-r)...f(i,a+r))である。
その他コストをb払うとf(i+1,a+r+b)≦f(i,a-r-b)+bとなる。
また、追加で半径を伸ばすことを考えるとf(i+1,x)≦f(i+1,x+1)≦f(i+1,x)+1なので、これをもとにf(i+1,x)を再計算するとよい。

int N,M;
pair<int,int> P[101];

ll dp[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	sort(P,P+N);
	
	FOR(j,M+1) dp[j+1]=1LL<<60;
	FOR(i,N) {
		for(j=0;j<P[i].first-P[i].second;j++) {
			dp[min(M,P[i].first+(P[i].first-j-1))]=min(dp[min(M,P[i].first+(P[i].first-j-1))],dp[j]+(P[i].first-j-1-P[i].second));
		}
		for(j=max(0,P[i].first-P[i].second-1);j<=min(M,P[i].first+P[i].second);j++) {
			dp[min(M,P[i].first+P[i].second)]=min(dp[min(M,P[i].first+P[i].second)],dp[j]);
		}
		for(j=1;j<M;j++) dp[j+1]=min(dp[j+1],dp[j]+1);
		for(j=M-1;j>=1;j--) dp[j]=min(dp[j+1],dp[j]);
		
	}
	cout<<dp[M]<<endl;
	
}

まとめ

Div2Dでもよさそう。