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

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1850 [NOIP 2016 提高组] 换教室 - 洛谷【题目描述】对于刚上大学的牛牛来说他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中有2 n 2n2n节课程安排在n nn个时间段上。在第i ii1 ≤ 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 ii1 ≤ 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 ii1 ≤ 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 ii1 ≤ 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 ii1 ≤ 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​≤v1 ≤ w j ≤ 100 1 \le w_j \le 1001≤wj​≤100。保证1 ≤ n ≤ 2000 1 \leq n \leq 20001≤n≤20000 ≤ m ≤ 2000 0 \leq m \leq 20000≤m≤20001 ≤ v ≤ 300 1 \leq v \leq 3001≤v≤3000 ≤ 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#【代码详解】#includebits/stdc.husingnamespacestd;constintN2005;// 最大天数constintM305;// 最大可申请换教室次数constintINF1e9;// 表示无穷大的值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(){// 输入基本数据cinnmve;// 初始化距离矩阵为无穷大memset(dist,0x3f,sizeof(dist));// 输入第i天原本应该去的教室for(inti1;in;i){cinc[i];}// 输入第i天可以申请的教室for(inti1;in;i){cind[i];}// 输入第i天申请成功的概率for(inti1;in;i){cink[i];}// 初始化距离矩阵自己到自己的距离为0for(inti1;i300;i){dist[i][i]0;}// 输入路径信息for(inti1;ie;i){inta,b,w;cinabw;dist[a][b]dist[b][a]min(dist[a][b],w);}// Floyd算法计算所有教室之间的最短距离for(intk1;kv;k){for(inti1;iv;i){for(intj1;jv;j){if(dist[i][k]dist[k][j]dist[i][j]){dist[i][j]dist[i][k]dist[k][j];}}}}// 初始化动态规划数组为无穷大for(inti1;in;i){for(intj0;jm;j){dp[i][j][0]dp[i][j][1]INF;}}// 初始化第一天的情况dp[1][0][0]0;// 第一天不申请dp[1][1][1]0;// 第一天申请// 动态规划for(inti2;in;i)// 从第二天开始{// 计算第i天不申请的情况for(intj0;jm;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(intj1;jm;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){doublevaldp[i-1][j-1][1];valk[i-1]*k[i]*dist[d[i-1]][d[i]];valk[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);}}}// 找到最小期望距离doubleansINF;for(intj0;jm;j){ansmin(ans,dp[n][j][0]);// 最后一天不申请ansmin(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