この問題は DP で解くことができます。

家の座標をソートし、 \(X\) は昇順であるとしてよいです。

\(\mathrm{DP}[i]\) を「家 \(1,2,\dots,i\) を全て照らすための最小費用」と定めます。

家 \(i\) までを全て照らせているとき、次に設置する街灯は、照らせる範囲の左端が家 \(i+1\) の位置になるように置くのが最適です。

よって、\(f(x)\) を「座標が \(x\) 以下であるような家の index の最大値」として

\(\mathrm{DP}[f(X_i+2R_j)]\xleftarrow{\mathrm{chmin}}\mathrm{DP}[i]+C_j\)

とする配る DP を行うことができます。\(f\) は二分探索により \(O(\log N)\) で求めることができるので、全体の計算量は \(O(NM\log N)\) となります。

なお \(f(X_i+2R_j)\) は \(j\) を固定するごとに \(i\) に関して単調なので、全ての \(i\) についてを \(O(N)\) で求めることができ、全体の計算量を \(O(NM)\) とすることもできます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<long long> x(n);
  for(int i=0; i<n; i++) cin >> x[i];
  sort(x.begin(), x.end());
  vector<pair<int,int>> rc(m);
  for(int i=0; i<m; i++) cin >> rc[i].first >> rc[i].second;

  vector<long long> dp(n+1, 1e18);
  dp[0] = 0;
  for(int i=0; i<n; i++){
    for(auto [r, c]: rc){
      int ii = upper_bound(x.begin(), x.end(), x[i]+2*r) - x.begin();
      dp[ii] = min(dp[ii], dp[i]+c);
    }
  }
  cout << dp.back() << endl;
}

実装例 (Python)

import bisect
N, M = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
RC = []
for _ in range(M):
  r, c = map(int, input().split())
  RC.append((r, c))

dp = [10**18]*(N+1)
dp[0] = 0
for i in range(N):
  for r, c in RC:
    ii = bisect.bisect_right(X, X[i]+2*r)
    dp[ii] = min(dp[ii], dp[i]+c)

print(dp[-1])