2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——L. Last Orders · znzryb
## 题目大意
**题目总结：L. Last Orders**
**1. 核心目标**
在所有酒吧关闭前，尽可能多地喝掉按顺序给出的品脱（Pints）。任务是计算最大可饮用数量。
**2. 场景规则**
- **起始状态**：时间为 0，位于 1 号酒吧。
- **饮酒消耗**：第 $i$ 杯酒需要花费时间 $t_i$。必须按 $t_1, t_2, \dots, t_r$ 的固定顺序饮用。
- **地点限制**：
- 全镇共有 $k$ 个酒吧（对应 $k$ 个交叉口）。
- **禁止连续在同一个酒吧喝两杯酒**（每喝完一杯，下一杯必须换到另一个酒吧，之后可以再回来）。
- **时间限制**：**每个酒吧 $i$ 有其绝对关门时间 $c_i$**。饮酒操作必须在酒吧关门**之前或准时**完成。
- **移动消耗**：**酒吧间通过 $m$ 条双向道路连接**，每条路有对应的行驶时间。
根据题目意思，**酒馆关闭仅意味着不能在这个地方饮酒**，**不意味着就是该节点无法通过**。
**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]=time
$$
转移采用分段转移的这个策略，就是每次只转移一步。
```go
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](https://qoj.ac/submission/2015239)
**源代码**
## 心路历程（WA，TLE，MLE……）
[https://qoj.ac/submission/2014564](https://qoj.ac/submission/2014564)
故意WA了一发，呃呃，这个是故意的。呃，我故意就是没有考虑到呃零节点，他呃就一节点他不喝酒的情况。