本博客主要解析Luogu P2577题目，探讨一个涉及双窗口的动态规划问题。在只有一个窗口时，问题简单，但当存在两个窗口时，需要考虑如何分配人员以达到最短总用餐时间。通过建立状态转移方程，将三维动态规划优化为二维，从而解决了空间限制问题。关键在于理解打饭时间固定，可以通过一个变量推导出另一个变量，降低了复杂度。
https://www.luogu.org/problemnew/show/P2577
题解
这其实是一个背包问题的变形，如果只有一个窗口的话，对于排队打饭的时间是固定的，那么只要按照谁吃的慢谁先上就可以得出最优值。
这道题有两个窗口，贪心的方法还是一样的，但是需要考虑分配问题。
设dp[i][j][k]: 下标：前i个人在窗口1花了j的打饭时间，在窗口2花了k的打饭时间。值: 前i个人最小的用餐时间。
设打饭时间为a，吃饭时间为b。
状态转移方程很容易写出来:
考虑决策：
- 第i个人打饭+吃饭的时间被前i-1个人的总时间覆盖。
- 第i个人打饭+吃饭的时间不被前i-1个人的总时间覆盖。
在窗口1打饭
d p [ i ] [ j ] [ k ] = m i n ( d p [ i ] [ j ] [ k ] , m a x ( d p [ i − 1 ] [ j − a ] [ k ] , j + b ) ) dp[i][j][k] = min(dp[i][j][k], max(dp[i-1][j-a][k], j+b) ) dp[i][j][k]=min(dp[i][j][k],max(dp[i−1][j−a][k],j+b))
在窗口2打饭
d p [ i ] [ j ] [ k ] = m i n ( d p [ i ] [ j ] [ k ] , m a x ( d p [ i − 1 ] [ j ] [ k − a ] , j + b ) ) dp[i][j][k] = min(dp[i][j][k], max(dp[i-1][j][k-a], j+b) ) dp[i][j][k]=min(dp[i
最低0.47元/天 解锁文章
扫一扫
350
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
