没参加。
https://leetcode.cn/problems/maximize-win-from-two-segments/
// 两条活动的线段，让人想到经典的“两数之和”
// 因此，先固定一条线段（或者说枚举这条线段），加上对应的另一条线段的最优值
//
// 本题中，可以想成固定右边的线段，辅以左边的对应的最优线段
// 因此无论如何都要先解决一条线段的问题
//
// pre[i+1] 表示线段右端点在 i 及其左侧最优的覆盖数
// 这里用 pre[i+1] 而非 per[i] 可以简化编程
class Solution {
public:
int maximizeWin(vector<int> &prizePositions, int k) {
int ans = 0, left = 0, n = prizePositions.size(), pre[n + 1];
pre[0] = 0;
for (int right = 0; right < n; right++) {
while (prizePositions[right] - prizePositions[left] > k) ++left;
ans = max(ans, right - left + 1 + pre[left]); // 端点在 right 的线段 + left 之前最右的话
pre[right + 1] = max(pre[right], right - left + 1); // 其实这里有点线性 DP 的味道
}
return ans;
}
};https://leetcode.cn/problems/disconnect-path-in-a-binary-matrix-by-at-most-one-flip/
// 灵神思路有点过于妙了
// 现在想象：
// 把所有通路描出来
// 然后我们走一条路到终点，把这条路上所有 g 标为 0
// 然后我们再走一次，如果还能走到终点，则说明不能靠改一个点阻止成为通路
// 如果走不到终点，则说明改一个点就能阻止成为通路，因为我们之前走的路只能是右与下
class Solution {
public:
bool isPossibleToCutPath(vector<vector<int>> &g) {
int m = g.size(), n = g[0].size();
function<bool(int, int)> dfs = [&](int x, int y) -> bool { // 返回能否到达终点
if (x == m - 1 && y == n - 1) return true;
g[x][y] = 0; // 直接修改
// 逻辑短路：如果 dfs(x + 1, y) 走得通，则没必要运行 dfs(x, y + 1)
return x < m - 1 && g[x + 1][y] && dfs(x + 1, y) ||
y < n - 1 && g[x][y + 1] && dfs(x, y + 1);
};
return !dfs(0, 0) || !dfs(0, 0);
}
};