Znzryb's Blog
0%

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——L. Last Orders

Posted on Edited on

题目大意

题目总结：L. Last Orders

1. 核心目标

在所有酒吧关闭前，尽可能多地喝掉按顺序给出的品脱（Pints）。任务是计算最大可饮用数量。

2. 场景规则

  • 起始状态：时间为 0，位于 1 号酒吧。

  • 饮酒消耗：第 ii 杯酒需要花费时间 tit_i。必须按 t1,t2,…,trt_1, t_2, \dots, t_r 的固定顺序饮用。

  • 地点限制：

    • 全镇共有 kk 个酒吧（对应 kk 个交叉口）。
    • 禁止连续在同一个酒吧喝两杯酒（每喝完一杯，下一杯必须换到另一个酒吧，之后可以再回来）。

  • 时间限制：每个酒吧 ii 有其绝对关门时间 cic_i。饮酒操作必须在酒吧关门之前或准时完成。

  • 移动消耗：酒吧间通过 mm 条双向道路连接，每条路有对应的行驶时间。

根据题目意思，酒馆关闭仅意味着不能在这个地方饮酒，不意味着就是该节点无法通过。

3. 样例解释

  • 样例 1：

    • 2 个酒吧，关门时间分别为 900 和 1500；酒吧 1 与 2 之间路程 90；饮酒时间序列为 60, 120, 180, 240…
    • 流程示例：
      1. 在酒吧 2 喝第 1 杯（路程 90 + 饮酒 60 = 150s ≤\le 1500，可行）。
      2. 回酒吧 1 喝第 2 杯（路程 90 + 饮酒 120 = 360s ≤\le 900，可行）。
      3. 回酒吧 2 喝第 3 杯（路程 90 + 饮酒 180 = 630s ≤\le 1500，可行）。
      4. 回酒吧 1 喝第 4 杯（路程 90 + 饮酒 240 = 960s）。此时 960 > 酒吧 1 的关门时间 900，无法在酒吧 1 喝第 4 杯。
    • 最终通过合理分配，最大可喝 4 杯。

  • 样例 2：

    • 饮酒时间非常短（2s 或 3s），但酒吧关门时间也非常早（15s 到 35s）。
    • 由于不能在同一酒吧连喝，必须频繁在 1、2、3、4 号酒吧之间切换（考虑路程 1 或 5），利用极短的饮酒时间在多个酒吧关门前完成饮用，最大可喝 7 杯。

思路讲解

这道题目还是没有那么难的。这个是我们所采用的这个状态定义。

dp[node][pint]=timedp[node][pint]=time

转移采用分段转移的这个策略，就是每次只转移一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
  ll ans=0;
  vector<vector<ll>> dp_old(N+3,vector<ll>(R+3,INF));
  //  第一个节点不喝酒，就从这里转移过来
  dp_old[1][0]=0;
  if (tim_drink[1]<=close_pub_tim[1]) {
// 第一个节点喝酒，就从这里转移
      dp_old[1][1]=tim_drink[1];
      ans=1;
  }
  for (int ci=1;ci<=R+1;++ci) {
      // 因为我们有最短路保证
      // 因此我们每次转移都必须喝酒，因为不喝酒，你来这个节点干什么？毕竟有最短路保证**
      // 不过第一个节点可以不喝酒。
      vector<vector<ll>> dp_new=dp_old;
      for (int u=1;u<=N;++u) {
    // 因为节点第一个节点可以喝酒，也可以不喝酒。所以说有的节点比别的节点转移稍微慢一拍，
    // 所以我们要照顾到转移稍微慢一拍的。所以我们从 ci 减一和 ci 转移。
          for (ll pint=ci-1;pint<=ci;++pint) {
              ll tim=dp_old[u][pint];
              for (int to=1;to<=N;++to) {
                  if (to==u) continue;
                  if (shortest_path[u][to]==INF) continue;
                  ll val=tim+shortest_path[u][to]+tim_drink[pint+1];
                  // 判断是否可以喝完这杯酒
                  if (val<=close_pub_tim[to]) {
                      dp_new[to][pint+1]=min(dp_new[to][pint+1],val);
                      ans=max(ans,pint+1);
                  }
              }
          }
      }
      swap(dp_new,dp_old);
  }
  ans=min(ans,R);
  cout<<ans<<"\n";

AC代码

AC
https://qoj.ac/submission/2015239

源代码

心路历程（WA，TLE，MLE……）

https://qoj.ac/submission/2014564

故意WA了一发，呃呃，这个是故意的。呃，我故意就是没有考虑到呃零节点，他呃就一节点他不喝酒的情况。