首页 > 其他 > 详细

P2577 [ZJOI2005]午餐

时间:2020-07-08 20:51:45      阅读:58      评论:0      收藏:0      [点我收藏+]

知识点: DP

原题面

不会真的有人 2h 一道绿题都调不出来吧,不会吧不会吧。
是我没错了


分析题意

设第 \(i\) 个人打饭时间,吃饭时间分别为 \(a_i\)\(b_i\),前 \(i\) 个人打饭时间总和为 \(sum_i\)

先考虑只排一队的情况,对于一给定的队列完成的时间,有:

\[time = \max_{i=1}^{n}\{sum_i+b_i\} \]

答案即为 最小的完成时间。

对于两个相邻的人, \(i\)\(i+1\),若 \(b_{i+1} > b_i\)

  • \(i+1\) 在后面时,两者完成时间分别为 \(sum_i + b_i, sum_i+a_{i+1}+b_{i+1}\)
    显然有 \(sum_i+a_{i+1}+b_{i+1}> sum_i + b_i\)
  • \(i+1\) 在前面时,完成时间分别为 \(sum_i+b_{i+1}, sum_{i} + a_i+b_i\)

显然有 \(sum_i+a_{i+1}+b_{i+1} > \max\{sum_i+b_{i+1}, sum_{i} + a_i+b_i\}\)

欲使 \(\max\limits_{i=1}^{n}\{sum_i+b_i\}\) 尽可能小,显然使 \(i+1\) 排在前面更优。

感性理解,吃饭慢的放在前面一定更优。
则可先将 \(n\) 个人按照吃饭时间降序排序。
逐个加入队列的人变成有序的了。
考虑线性 DP 求解此题。


发现有两边,不好设状态。
考虑 P1973 的思路,枚举一边的答案,并求另一边答案的最小值,两边取 \(max\) 即为所求。
\(f_{i,j,k}\) 表示 \(1\sim i\) 中,窗口一最后一个人为 \(j\),完成时间为 \(k\) 时,窗口二的完成时间。

然后发现无法转移,因为最后一个人不一定 最晚吃完。
陷入思考...

技术分享图片

手搓的心心.png


发现窗口二的队列,必定为窗口一的补集。

设当前第 \(i\) 个人加入队列,令窗口一队列打饭时间总和为 \(j\),则窗口二打饭时间总和为 \(sum_i - j\)

若已知 \(j\),可计算第 \(i\) 个人加入窗口一/二的完成时间。
考虑枚举窗口一打饭时间总和 \(j\),来更新答案。

\(f_{i,j}\) 表示,前 \(i\) 个人加入队列,窗口一队列打饭时间总和为 \(j\)时,两窗口的最小完成时间。

考虑第 \(i\) 个人排到窗口一/二:

  1. 排到窗口一,\(f_{i,j} = \max\{j + b_i,\ f_{i-1,j-a_i}\}\)
    \(j + b_i\) 为新加入窗口一的人的完成时间。
    \(f_{i-1,j-a_i}\) 为:不加此人时,窗口一的完成时间 与 窗口二的完成时间 的最小值,用于更新答案,不会导致漏解。
  2. 排到窗口二,\(f_{i,j} = \max\{f_{i-1,j},\ sum_i-j+b_i\}\)
    \(sum_i-j+b_i\) 为新加入窗口二的人的完成时间。
    \(f_{i-1,j}\) 也为不加此人时,窗口一的完成时间 与 窗口二的完成时间 的最小值。

上述两种情况取最小值即可。
复杂度 \(O(nT)\) (\(T\) 为最大时间),期望得分 \(100\text{pts}\)


代码实现

//知识点:DP
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define min std::min
#define max std::max
#define ll long long
const int kMaxn = 210;
const int kInf = 1e9 + 2077;
//=============================================================
struct Data {
  int a, b;
} d[kMaxn];
int n, ans = kInf, sum[kMaxn], f[kMaxn][kMaxn * kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ ‘0‘);
  return f * w;
}
bool Compare(Data fir, Data sec) {
  return fir.b > sec.b;
}
//=============================================================
int main() {
  n = read();
  for (int i = 1; i <= n; ++ i) {
    d[i].a = read(), d[i].b = read();
  }
  std :: sort(d + 1, d + n + 1, Compare);
  memset(f, 63, sizeof(f));
  f[0][0] = 0;
  for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + d[i].a;
  for (int i = 1; i <= n; ++ i) {
    int a = d[i].a, b = d[i].b;
    for (int j = 1; j <= sum[i]; ++ j) {
      f[i][j] = max(f[i - 1][j], sum[i] - j + b);
      if (j - a >= 0) f[i][j] = min(f[i][j], max(f[i - 1][j - a], j + b));
    }
  }
  for (int i = 1; i <= sum[n]; ++ i) {
    ans = min(ans, f[n][i]);
  }
  printf("%d\n", ans);
  return 0;
}

P2577 [ZJOI2005]午餐

原文:https://www.cnblogs.com/luckyblock/p/13268758.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!