链接
题意
给出$n$个主题,给出每节课的长度$L$和不满意度参数$C$,要安排课程。要求单个主题不能拆分在两节课上,主题间的顺序不能打乱。另外每堂课根据剩余时间$x$有不同不满意度:
- 当$x = 0$时,不满意度为0;
- 当$1 \leq x \leq 10$时,不满意度为$-C$;
- 当$x \geq 11$时,不满意度为$(x - 10) ^ 2$。
输出最少安排课程的节数,和最小的不满意度。
思路
定义状态$d[i][j]$为上$i$节课,讲到第$j$个主题时最小的不满意度。对于$d[i][j]$如果第$k$个主题连续讲到第$j$个主题可以在一节课之内完成,则可以从$dp[i - 1][k]$转移。
代码
|
|