企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1850 [NOIP 2016 提高组] 换教室 - 洛谷

【题目描述】

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有2 n 2n2n节课程安排在n nn个时间段上。在第i ii（1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室c i c_ici​上课，而另一节课程在教室d i d_idi​进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的n nn节安排好的课程。如果学生想更换第i ii节课程的教室，则需要提出申请。若申请通过，学生就可以在第i ii个时间段去教室d i d_idi​上课，否则仍然在教室c i c_ici​上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第i ii节课程的教室时，申请被通过的概率是一个已知的实数k i k_iki​，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多m mm节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的m mm门课程，也可以不用完这m mm个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有v vv个教室，有e ee条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第i ii（1 ≤ i ≤ n − 1 1 \leq i \leq n-11≤i≤n−1）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

【输入】

第一行四个整数n , m , v , e n,m,v,en,m,v,e。n nn表示这个学期内的时间段的数量；m mm表示牛牛最多可以申请更换多少节课程的教室；v vv表示牛牛学校里教室的数量；e ee表示牛牛的学校里道路的数量。

第二行n nn个正整数，第i ii（1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n）个正整数表示c i c_ici​，即第i ii个时间段牛牛被安排上课的教室；保证1 ≤ c i ≤ v 1 \le c_i \le v1≤ci​≤v。

第三行n nn个正整数，第i ii（1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n）个正整数表示d i d_idi​，即第i ii个时间段另一间上同样课程的教室；保证1 ≤ d i ≤ v 1 \le d_i \le v1≤di​≤v。

第四行n nn个实数，第i ii（1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n）个实数表示k i k_iki​，即牛牛申请在第i ii个时间段更换教室获得通过的概率。保证0 ≤ k i ≤ 1 0 \le k_i \le 10≤ki​≤1。

接下来e ee行，每行三个正整数a j , b j , w j a_j, b_j, w_jaj​,bj​,wj​，表示有一条双向道路连接教室a j , b j a_j, b_jaj​,bj​，通过这条道路需要耗费的体力值是w j w_jwj​；保证1 ≤ a j , b j ≤ v 1 \le a_j, b_j \le v1≤aj​,bj​≤v，1 ≤ w j ≤ 100 1 \le w_j \le 1001≤wj​≤100。

保证1 ≤ n ≤ 2000 1 \leq n \leq 20001≤n≤2000，0 ≤ m ≤ 2000 0 \leq m \leq 20000≤m≤2000，1 ≤ v ≤ 300 1 \leq v \leq 3001≤v≤300，0 ≤ e ≤ 90000 0 \leq e \leq 900000≤e≤90000。

保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。

保证输入的实数最多包含3 33位小数。

【输出】

输出一行，包含一个实数，四舍五入精确到小数点后恰好2 22位，表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于4 × 10 − 3 4 \times 10^{-3}4×10−3。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）

【输入样例】

3 2 3 3 2 1 2 1 2 1 0.8 0.2 0.5 1 2 5 1 3 3 2 3 1

【输出样例】

2.80

【算法标签】

#提高+# #期望DP#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=2005;// 最大天数constintM=305;// 最大可申请换教室次数constintINF=1e9;// 表示无穷大的值intn,m,v,e;// n: 天数, m: 可申请次数, v: 教室数量, e: 路径数量intc[N];// 第i天原本应该去的教室intd[N];// 第i天可以申请的教室doublek[N];// 第i天申请成功的概率intdist[M][M];// 教室之间的最短距离doubledp[N][N][2];// 动态规划数组intmain(){// 输入基本数据cin>>n>>m>>v>>e;// 初始化距离矩阵为无穷大memset(dist,0x3f,sizeof(dist));// 输入第i天原本应该去的教室for(inti=1;i<=n;i++){cin>>c[i];}// 输入第i天可以申请的教室for(inti=1;i<=n;i++){cin>>d[i];}// 输入第i天申请成功的概率for(inti=1;i<=n;i++){cin>>k[i];}// 初始化距离矩阵，自己到自己的距离为0for(inti=1;i<=300;i++){dist[i][i]=0;}// 输入路径信息for(inti=1;i<=e;i++){inta,b,w;cin>>a>>b>>w;dist[a][b]=dist[b][a]=min(dist[a][b],w);}// Floyd算法计算所有教室之间的最短距离for(intk=1;k<=v;k++){for(inti=1;i<=v;i++){for(intj=1;j<=v;j++){if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}// 初始化动态规划数组为无穷大for(inti=1;i<=n;i++){for(intj=0;j<=m;j++){dp[i][j][0]=dp[i][j][1]=INF;}}// 初始化第一天的情况dp[1][0][0]=0;// 第一天不申请dp[1][1][1]=0;// 第一天申请// 动态规划for(inti=2;i<=n;i++)// 从第二天开始{// 计算第i天不申请的情况for(intj=0;j<=m;j++)// 枚举申请次数{// 情况1: 第i-1天不申请，第i天不申请dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+dist[c[i-1]][c[i]]);// 情况2: 第i-1天申请，第i天不申请if(dp[i-1][j][1]<INF){dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+k[i-1]*dist[d[i-1]][c[i]]+(1-k[i-1])*dist[c[i-1]][c[i]]);}}// 计算第i天申请的情况for(intj=1;j<=m;j++)// 枚举申请次数（至少需要一次申请）{// 情况3: 第i-1天不申请，第i天申请if(dp[i-1][j-1][0]<INF){dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+k[i]*dist[c[i-1]][d[i]]+(1-k[i])*dist[c[i-1]][c[i]]);}// 情况4: 第i-1天申请，第i天申请if(dp[i-1][j-1][1]<INF){doubleval=dp[i-1][j-1][1];val+=k[i-1]*k[i]*dist[d[i-1]][d[i]];val+=k[i-1]*(1-k[i])*dist[d[i-1]][c[i]];val+=(1-k[i-1])*k[i]*dist[c[i-1]][d[i]];val+=(1-k[i-1])*(1-k[i])*dist[c[i-1]][c[i]];dp[i][j][1]=min(dp[i][j][1],val);}}}// 找到最小期望距离doubleans=INF;for(intj=0;j<=m;j++){ans=min(ans,dp[n][j][0]);// 最后一天不申请ans=min(ans,dp[n][j][1]);// 最后一天申请}// 输出结果，保留2位小数printf("%.2lf\n",ans);return0;// 程序正常结束}

【运行结果】

3 2 3 3 2 1 2 1 2 1 0.8 0.2 0.5 1 2 5 1 3 3 2 3 1 2.80