题干：
题目大意：
题意是在一条直线上坐落着不同位置的灯塔，每一个灯塔有自己的power level，当作是射程范围。现在从最右边的灯塔开始激发，如果左边的灯塔在这个灯塔的范围之内，那么将会被毁灭。否则会被激发，留下自己。
解题报告：
dp求解：
现在可以从右边放置一个灯塔，位置和power level都可以自己定义。问各种情况中最小的灯塔被毁灭的数量。
dp[x]表示到x个灯塔的时候毁灭的最小数量。对于第x个灯塔来说，求出不再自己范围内的上一个的灯塔位置i，因此在自己范围内的灯塔数量也能够得知x-i+1。
那么会有dp[x]=dp[i]+x-i+1。这个是在第x炸弹被激发的情况下，毁灭的灯塔数量。
而今，因为可以在右边放置一个灯塔了。所以就求出dp[i]+(n-i) (1<=i<=n)的最小值。
AC代码1：（标解dp）
AC代码2：（二分）
#include<bits/stdc++.h>
using namespace std;
pair<int,int> pr[100000 + 5];
int dp[100000 + 5];
int main() {
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d%d",&pr[i].first,&pr[i].second);
}
sort(pr+1,pr+n+1);
dp[0]=0;
// pr[n+1].first=-1;
for(int i = 1; i<=n; i++) {
int loc = lower_bound(pr+1,pr+i+1,make_pair(pr[i].first - pr[i].second,-1)) - pr;
if(loc)
dp[i] = dp[loc - 1] + (i-loc);
else dp[i] = i-1;
// printf("%d = %d\n",i,dp[i]);
}
int minn = 0x3f3f3f3f;
for(int i = 1; i<=n; i++) {
minn = min(minn,dp[i] + (n-i) );
}
printf("%d\n",minn);
return 0 ;
} AC代码3：（网络版的二分，跟第二个差不多）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3fffffff
const int maxn = 100005;
int n;
int dp[maxn];//记录毁灭的最小值
struct no {
int a;
int b;
} node[maxn];
bool cmp(const no &n1, const no &n2) {
return n1.a < n2.a;
}
void solve() {
int i;
sort(node + 1, node + n + 1, cmp);
for (i = 1; i <= n; i++) {
no nx;
nx.a = node[i].a - node[i].b;
int pos = lower_bound(node + 1, node + n + 1, nx, cmp) - node;
if (pos)
dp[i] = dp[pos - 1] + (i - pos);//因为最靠右的会被激发，致使范围之内的会被毁灭
else
dp[i] = i - 1;//除了自己全部毁灭
// printf("%d = %d\n",i,dp[i]);
}
int res = n;
for (i = 1; i <= n; i++) {
res = min(res, dp[i] + (n - i));
}
printf("%d", res);
}
int main() {
scanf("%d",&n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &node[i].a, &node[i].b);
}
solve();
return 0;
}
依旧二分AC4：
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int dp[MAX];
pair<int,int> pr[MAX];
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d%d",&pr[i].first,&pr[i].second);
}
sort(pr+1,pr+n+1);
dp[1]=1;//记录存活个数
// dp[0]=0;
for(int i = 2; i<=n; i++) {
if(pr[i].first - pr[i].second <=0) {dp[i]=1;continue;}
int pos = lower_bound(pr+1,pr+i+1,make_pair(pr[i].first - pr[i].second,-1)) - pr;//会被辐射到的
pos--;//第一个不会被辐射到的
dp[i] = dp[pos]+1;
}
int minn = 0x3f3f3f3f;
for(int i = 1; i<=n; i++) {
//minn = min(minn,n - i + (i-dp[i]));
minn = min(minn,n-dp[i]);
}
printf("%d\n",minn);
return 0 ;
} 依旧二分AC5：
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int dp[MAX];
pair<int,int> pr[MAX];
int main()
{
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%d%d",&pr[i].first,&pr[i].second);
}
sort(pr+1,pr+n+1);
// dp[1]=1;//记录存活个数
dp[0]=0;
for(int i = 1; i<=n; i++) {//这里是从1开始了、、、
// if(pr[i].first - pr[i].second <=0) {dp[i]=1;continue;}
int pos = lower_bound(pr+1,pr+i+1,make_pair(pr[i].first - pr[i].second,-1)) - pr;//会被辐射到的
pos--;//第一个不会被辐射到的
dp[i] = dp[pos]+1;
}
int minn = 0x3f3f3f3f;
for(int i = 1; i<=n; i++) {
//minn = min(minn,n - i + (i-dp[i]));
minn = min(minn,n-dp[i]);
}
printf("%d\n",minn);
return 0 ;
} ps：其实上面几个代码都可以lowerbound(pr+1 , pr+i , ....) - pr 就行了，不需要pr+i+1.。。但是其实好像是一模一样的。（本以为可以不用判断pos的结果等于pre的情况（也就是一个都没找到 的情况），但是发现这样写也是要考虑的，因为你pr+i的话，lowerbound没找到也是要返回pos==pre这个的啊，结合那个【CodeForces - 799C】Fountains去理解下、、）
二分网络版AC代码6：（其实跟AC代码4是一样的）
//meek///#include<bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<bitset>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define fi first
#define se second
#define MP make_pair
typedef long long ll;
const int N = 201000;
const int M = 1000001;
const int inf = 0x3f3f3f3f;
const int MOD = 100003;
const double eps = 0.000001;
struct ss{
int p,s,S;
}a[N];
int n,b[N],H[N],t[M],sum[N],dp[M+5];
int cmp(ss s1,ss s2) {return s1.p<s2.p;}
int main () {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&a[i].p,&a[i].s);
a[i].S=a[i].p-a[i].s-1;
}
int cnt=0; int tmp;
sort(a+1,a+n+1,cmp);
int ans=0,L=0;
int cc=1;
for(int i=0;i<=M;i++) {
if(i==a[cc].p) {
if(a[cc].S>=0) {
dp[i] = dp[a[cc].S] +1;
}
else dp[i] = 1;
cc++;
}
else dp[i] = dp[i-1];
ans=max(dp[i],ans);
// cout<<dp[i]<<endl;
}
cout<<n-ans<<endl;
return 0;
}
daima 标解dp代码7：（wlb）
#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
#define INF 0x3fffffff
const int maxn = 1000005;
int n, nmax;
int dp[maxn];
int d[maxn];//记录能够存活的最大值
void input() {
int i, a;
scanf("%d", &n);
nmax = 0;
for (i = 1; i <= n; i++) {
scanf("%d", &a);//记录炸弹位置
scanf("%d", &d[a]);//记录该位置炸弹的范围
nmax = max(a, nmax);
}
}
void solve() {
int i;
if (d[0])
dp[0] = 1;
int res = n;
res = min(res, n - dp[0]);
for (i = 1; i <= nmax; i++) {
if (d[i] == 0) {
dp[i] = dp[i - 1];//如果该位置没有炸弹
} else {
if (d[i] >= i) {
dp[i] = 1;//这个位置只剩下一个了
} else {
dp[i] = dp[i - d[i] - 1] + 1;//表示在该炸弹的范围内只存活了自己，所以在之前的位置加1
}
}
res = min(res, n - dp[i]);
}
printf("%d", res);
}
int main() {
//freopen("i.txt", "r", stdin);
//freopen("o.txt", "w", stdout);
input();
solve();
//system("pause");
return 0;
}
超时代码：
#include<bits/stdc++.h>
using namespace std;
int pos[100000 + 5],b[100000 +5];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i<=n; i++) {
scanf("%d %d",&pos[i],&b[i]);
}
int loc,ans,minn = 0x3f3f3f3f;
for(int i = n; i>=1; i--) {
loc = i;
ans = 0;
while(loc > 1) {
int pre = loc;
if(pos[loc] - pos[loc-1] > b[loc]) {
loc--;continue;
}
loc = lower_bound(pos+1,pos+loc+1,pos[loc] - b[loc]) - pos;
if(loc == pre) continue;
ans += (pre - loc );
loc--;
}
minn = min(minn,ans + (n-i));
// printf("mi = %d\n",minn);
}
printf("%d\n",minn);
return 0 ;
}
//4
//1 9
//3 1
//6 1
//7 4
京公网安备 11010502036488号