第一场团队赛：Nordic Collegiate Programming Contest 2019
训练记录--比赛记录

求01矩阵中最大的全为0或1的矩阵

• 还是 数据结构专题

• https://codeforces.com/contest/1353
• Codeforces Round 642 (Div. 3)

本周只打了例行的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)