题目链接:https://codeforces.com/contest/1253/my
题目大意:
m个天线,每个天线的位置是xi,分数是si,覆盖范围是[xi−si;xi+si],每个硬币可以使一个天线的si+1,求覆盖整个[1;m]的最少硬币
思路:
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
int f[N],s[N],x[N];
int main()
{
int n,m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
f[i]=1<<30;
}
f[0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> s[i];
}
for (int i = 1; i<= m; i++){
for (int j = 1; j <= n;j++){
if ( i >= x[j])
{
f[i] = min(f[i],f[max(2*x[j]-i-1,0)]+max(i-x[j]-s[j],0));
f[i] = min(f[i], max(2*x[j]-i-1,0)+max(i-x[j]-s[j],0));
}
else
{
f[i] = min(f[i],f[max(x[j]-s[j]-1,0)]);
f[i] = min(f[i],max(x[j]-s[j]-1,0));
}
}
}
cout << f[m] << endl;
return 0;
}