首页 > [NOIP2016]换教室
开通博客写题解
头像 savage
发表于 2019-09-02 14:41:57
题目描述 对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中，有 2n 节课程安排在 n 个时间段上。在第 i （1 ≤ i ≤ n）个时间 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 henry_y
发表于 2019-09-02 20:11:19
题目地址 https://www.luogu.org/problem/P1850 题解 这题的转移其实挺好想的但是方程特别长...真的特别长...首先设表示当前在第个位置，申请了次，当前这次申请了/没申请，为当前被安排的课室位置，为可申请的课室位置，为申请通过的概率，表示到的最短路。 直接一遍求出来 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 savage
发表于 2019-09-07 17:09:08
算法知识点: 数学期望,动态规划 复杂度： 解题思路： 状态表示： f[i][j][0]表示前i个课程，申请换了j次，且最后一次没申请换的最小期望长度 f[i][j][1]表示前i个课程，申请换了j次，且最后一次申请交换的最小期望长度 则f[ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 氧气少年Kevin
发表于 2022-11-09 20:31:30
概率期望 洛谷1850 - 换教室 https://www.luogu.com.cn/problem/P1850 难度：蓝 题意 有 nnn 节课。学生需要按顺序依次完成所有的 nnn 节课。 若不提交申请，时刻 iii 学生需要在 cic_ici​ 的教室上课。 学生可以申请将教室更改为 d 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”