2020/5/11-2020/5/17
团队训练
队伍知识点
吕双羽
专题
- 还是 数据结构专题
比赛
吴湛宇
本周只打了例行的ACM模拟赛[手动捂脸]，下次一定
陶虹宇
本周只打了例行的ACM模拟赛[手动捂脸]，下次一定
本周推荐
吕双羽
Codeforces Round 642 (Div. 3) F：https://codeforces.com/problemset/problem/1353/F
题意：单元格（1，1）中，想进入单元格（n，m）。只能向下（从单元格（i，j）移动到单元格（i+1，j））或向右（从单元格（i，j）移动到单元格（i，j+1））。还有一个附加限制：如果当前单元格的高度为x，则只能移动到高度为x+1的单元格。在第一次移动之前，您可以执行多个操作。在一次操作中，可以将任何单元格的高度减少一个。找到从单元格（1,1）到单元格（n，m）的至少一条合适路径所需执行的最少操作数。答案一定存在。
思路：当(1,1)高度固定时，由于只能向右和向下，从(1,1)到任意(i,j)的距离是唯一的，因此h[i][j]也是确定的，所以使用dp求解。dp[i][j]=min(dp[i-1][j]+dp[i][j-1])+(a[i][j]-a[1][1]-i-j+2)但是如果我们遍历所有可能的高度，我们的解显然会得到超过时间限制的结论。现在我们可以注意到一个重要的事实：在最佳答案中，某些单元格的高度保持不变。因此枚举这些可能的高度即可。时间复杂度O(n^4)
吴湛宇
差分约束：有m个形如\(a_i-a_j \le k\)的限制条件，求\(a_n-a_1\)的最大值
解法：\(a_i-a_j \le k\)与最短路中的 \(f_i \le f_j+dis_{i,j}\)类似 因此可以由j向i连一条长度为k的单向边，spfa跑一边最短路即可得到最大值。
如果存在负环，则说明无解
如果限制条件中存在大于等于，则两边同时乘以-1
如果存在等于，则变为大于等于&&小于等于
