杭州制作企业公司网站,wordpress数据库添加用户,wordpress备案信息,专业设计网站公司题干#xff1a; 题目大意#xff1a;
题意是在一条直线上坐落着不同位置的灯塔#xff0c;每一个灯塔有自己的power level#xff0c;当作是射程范围。现在从最右边的灯塔开始激发#xff0c;如果左边的灯塔在这个灯塔的范围之内#xff0c;那么将会被毁灭。否则会被激…题干 题目大意
题意是在一条直线上坐落着不同位置的灯塔每一个灯塔有自己的power level当作是射程范围。现在从最右边的灯塔开始激发如果左边的灯塔在这个灯塔的范围之内那么将会被毁灭。否则会被激发留下自己。
解题报告
dp求解
现在可以从右边放置一个灯塔位置和power level都可以自己定义。问各种情况中最小的灯塔被毁灭的数量。
dp[x]表示到x个灯塔的时候毁灭的最小数量。对于第x个灯塔来说求出不再自己范围内的上一个的灯塔位置i因此在自己范围内的灯塔数量也能够得知x-i1。
那么会有dp[x]dp[i]x-i1。这个是在第x炸弹被激发的情况下毁灭的灯塔数量。
而今因为可以在右边放置一个灯塔了。所以就求出dp[i](n-i) (1in)的最小值。
AC代码1标解dp AC代码2二分
#includebits/stdc.husing namespace std;
pairint,int pr[100000 5];
int dp[100000 5];
int main() {int n;cinn;for(int i 1; in; i) {scanf(%d%d,pr[i].first,pr[i].second);}sort(pr1,prn1);dp[0]0;
// pr[n1].first-1;for(int i 1; in; i) {int loc lower_bound(pr1,pri1,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; in; i) {minn min(minn,dp[i] (n-i) );}printf(%d\n,minn);return 0 ;
}
AC代码3网络版的二分跟第二个差不多
#includebits/stdc.h
using namespace std;
typedef long long ll;
#define INF 0x3fffffffconst 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);//因为最靠右的会被激发致使范围之内的会被毁灭elsedp[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
#includebits/stdc.husing namespace std;
const int MAX 1e5 5;
int dp[MAX];
pairint,int pr[MAX];
int main()
{int n;cinn;for(int i 1; in; i) {scanf(%d%d,pr[i].first,pr[i].second);}sort(pr1,prn1);dp[1]1;//记录存活个数
// dp[0]0;for(int i 2; in; i) {if(pr[i].first - pr[i].second 0) {dp[i]1;continue;}int pos lower_bound(pr1,pri1,make_pair(pr[i].first - pr[i].second,-1)) - pr;//会被辐射到的 pos--;//第一个不会被辐射到的dp[i] dp[pos]1;}int minn 0x3f3f3f3f;for(int i 1; in; i) {//minn min(minn,n - i (i-dp[i]));minn min(minn,n-dp[i]);}printf(%d\n,minn);return 0 ;}
依旧二分AC5
#includebits/stdc.husing namespace std;
const int MAX 1e5 5;
int dp[MAX];
pairint,int pr[MAX];
int main()
{int n;cinn;for(int i 1; in; i) {scanf(%d%d,pr[i].first,pr[i].second);}sort(pr1,prn1);
// dp[1]1;//记录存活个数 dp[0]0;for(int i 1; in; i) {//这里是从1开始了、、、
// if(pr[i].first - pr[i].second 0) {dp[i]1;continue;}int pos lower_bound(pr1,pri1,make_pair(pr[i].first - pr[i].second,-1)) - pr;//会被辐射到的 pos--;//第一个不会被辐射到的dp[i] dp[pos]1;}int minn 0x3f3f3f3f;for(int i 1; in; i) {//minn min(minn,n - i (i-dp[i]));minn min(minn,n-dp[i]);}printf(%d\n,minn);return 0 ;}
ps其实上面几个代码都可以lowerbound(pr1 , pri , ....) - pr 就行了不需要pri1.。。但是其实好像是一模一样的。本以为可以不用判断pos的结果等于pre的情况也就是一个都没找到 的情况但是发现这样写也是要考虑的因为你pri的话lowerbound没找到也是要返回pospre这个的啊结合那个【CodeForces - 799C】Fountains去理解下、、
二分网络版AC代码6其实跟AC代码4是一样的
//meek///#includebits/stdc.h
#include cstdio
#include cmath
#include cstring
#include algorithm
#includeiostream
#includebitset
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[M5];
int cmp(ss s1,ss s2) {return s1.ps2.p;}int main () {scanf(%d,n);for(int i1;in;i) {scanf(%d%d,a[i].p,a[i].s);a[i].Sa[i].p-a[i].s-1;}int cnt0; int tmp;sort(a1,an1,cmp);int ans0,L0;int cc1;for(int i0;iM;i) {if(ia[cc].p) {if(a[cc].S0) {dp[i] dp[a[cc].S] 1;}else dp[i] 1;cc;}else dp[i] dp[i-1];ansmax(dp[i],ans);// coutdp[i]endl;}coutn-ansendl;return 0;
}daima
标解dp代码7wlb
#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 0x3fffffffconst 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;
}超时代码
#includebits/stdc.husing namespace std;
int pos[100000 5],b[100000 5];
int main()
{int n;scanf(%d,n);for(int i 1; in; i) {scanf(%d %d,pos[i],b[i]);}int loc,ans,minn 0x3f3f3f3f;for(int i n; i1; i--) {loc i;ans 0;while(loc 1) {int pre loc;if(pos[loc] - pos[loc-1] b[loc]) {loc--;continue;}loc lower_bound(pos1,posloc1,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
