温州建设信息网站专门做讲座的英语网站

温州建设信息网站,专门做讲座的英语网站,常州市做网站,赣州建站服务本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来#xff0c;并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构#xff0c;旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。 欢迎大…本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10934 西瓜种植 - 洛谷【题目描述】笨笨种了一块西瓜地但这块西瓜地的种植范围是一条直线的……笨笨在一番研究过后得出了m mm个结论这m mm个结论可以使他收获的西瓜最多。笨笨的结论是这样的从西瓜地b bb处到e ee处至少要种植t tt个西瓜这个范围的收获就可以最大化。笨笨不想那么辛苦所以他想种植的西瓜尽量少而又满足每一个所得的结论。【输入】第一行两个数n nn,m mm0 n ≤ 5000 0n \le 50000n≤50000 ≤ m ≤ 3000 0 \le m\le 30000≤m≤3000表示笨笨的西瓜地长n nn笨笨得出m mm个结论。接下来m mm行表示笨笨的m mm个结论每行三个数b bb,e ee,t tt1 ≤ b ≤ e ≤ n 1 \le b\le e\le n1≤b≤e≤n0 ≤ t ≤ e − b 1 0 \le t\le e-b10≤t≤e−b1。【输出】输出笨笨最少需种植多少西瓜。【输入样例】9 4 1 4 2 4 6 2 8 9 2 3 5 2【输出样例】5【算法标签】《洛谷 P10934 西瓜种植》 #贪心# #差分约束#【代码详解】#includebits/stdc.husingnamespacestd;constintN5005,MN*3;// 最大顶点数和边数inth[N],e[M],w[M],ne[M],idx;// 链式前向星存储图intdist[N];// 最长距离数组boolst[N];// 标记顶点是否在队列中intn,m;// n: 范围[0,n], m: 区间约束数量/** * 添加有向边 * param a 起点 * param b 终点 * param c 权重 */voidadd(inta,intb,intc){e[idx]b;// 边指向的顶点w[idx]c;// 边的权重ne[idx]h[a];// 指向原链表头h[a]idx;// 更新头指针}/** * SPFA算法求最长路径 * 从顶点0开始计算到所有顶点的最长路径 */voidspfa(){// 初始化距离为负无穷memset(dist,-0x3f,sizeof(dist));memset(st,0,sizeof(st));queueintq;// SPFA队列q.push(0);// 起点入队st[0]true;// 标记在队列中dist[0]0;// 起点距离为0while(!q.empty()){inttq.front();// 取出队首q.pop();st[t]false;// 标记不在队列中// 遍历t的所有邻接边for(intih[t];i!-1;ine[i]){intje[i];// 邻接顶点// 松弛操作求最长路径if(dist[j]dist[t]w[i]){dist[j]dist[t]w[i];// 更新最长距离// 如果j不在队列中入队if(!st[j]){q.push(j);st[j]true;}}}}}intmain(){// 输入n和区间约束数量mcinnm;// 初始化邻接表memset(h,-1,sizeof(h));// 添加基础约束边// 顶点编号0~n共n1个顶点for(inti1;in;i){// 约束1: S_i - S_{i-1} ≤ 1// 即: S_{i-1} - S_i ≥ -1// 建边: i → i-1权重-1add(i,i-1,-1);// 约束2: S_i ≥ S_{i-1}// 即: S_i - S_{i-1} ≥ 0// 建边: i-1 → i权重0add(i-1,i,0);}// 添加区间约束while(m--){intb,e,t;cinbet;// 约束: S_e - S_{b-1} ≥ t// 即: S_e ≥ S_{b-1} t// 建边: b-1 → e权重tadd(b-1,e,t);}// 执行SPFA算法求最长路径spfa();// 输出从0到n的最长路径长度coutdist[n]endl;return0;}【运行结果】9 4 1 4 2 4 6 2 8 9 2 3 5 2 5