知识点: DP

原题面

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

分析题意

设第 \(i\) 个人打饭时间，吃饭时间分别为 \(a_i\) 与 \(b_i\)，前 \(i\) 个人打饭时间总和为 \(sum_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