大佬教程收集整理的这篇文章主要介绍了CF607A Chain Reaction【dp+二分】，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
原题链接
给定 (n) 个激光塔，每个激光塔有一个坐标 (a_i) 和一个威力 (b_i)，当第 (i) 个激光塔被激活后，坐标 (geq a_i-b_i) 的激光塔将被摧毁。现在在所有激光塔的右侧放置一个坐标和威力任意的激光塔，从右到左依次激活没有被摧毁的激光塔，求最少要摧毁多少个激光塔。
首先注意，虽然样例中的 (a_i) 都是升序给出的，但是题目中并未保证 (a_i) 升序，所以在最开始要进行排序。
定义 (f[i]) 表示以第 (i) 个激光塔为起点，依次向右激活没被摧毁的激光塔，摧毁的激光塔数量。注意这里不能定义为最小值，因为本题中的起点一旦确定，那么摧毁的数量也就确定了。
注意到题目中给出的最右侧的激光塔的威力任意，其实就可以转化为摧毁第 (i+1) 个到第 (n) 个激光塔后，再以第 (i) 个激光塔为起点向右激活。那么最终的答案就是 (min(f[i]+n-i))。
接下来考虑状态转移方程。注意到，第 (i) 个激光塔被激活后，下一个被激活的肯定是第一个坐标小于 (a_i-b_i) 的激光塔，同时因为坐标是单调递增的，就可以用二分来查找这个激光塔 (j)。那么状态转移方程就是 (f[i]=f[j]+i-j-1)。因为在 (j) 和 (i) 之间的激光塔显然被摧毁了。
#include<cstdio>
#include<algorithm>
using namespace std;
const int n=1e5+10;
const int INF=0x3f3f3f3f;
struct NLC{
int a,b;
bool operator <(const NLC &t)const{
return a<t.a;
}
}p[n];
int ans=INF,n,f[n];
int find(int X)
{
int l=1,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(p[mid].a<X) l=mid;
else r=mid-1;
}
return p[l].a<x?l:0;
}
int min(int a,int b){return a<b?a:b;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&p[i].a,&p[i].b);
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)
{
int j=find(p[i].a-p[i].b);
f[i]=f[j]+i-j-1;
ans=min(ans,f[i]+n-i);
}
printf("%dn",ans);
return 0;
}
以上是大佬教程为你收集整理的CF607A Chain Reaction【dp+二分】全部内容，希望文章能够帮你解决CF607A Chain Reaction【dp+二分】所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。