K-01BFS（2023河南萌新联赛第（五）场：郑州轻工业大学）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

思路：

直接枚举这个图中的拐点

这个拐点是经过左右平移到上下平移或者上下平移到左右平移

假设这个点事左到右后然后再从下到上

左到右就相当于走了个最长上升子序列，然后再从下到上

从下到上的过程你可以反过来看，就是从上走到下，就相当从上到下走了个最长下降子序列

然后最长上升/下降子序列可以用dp+二分来求

按题解的话来说就是

预处理出对于每个单元格四个方向上最多跳多少个单元格可以跳到当前单元格(最长上升子序列)，以及从当前单元格跳出最多能跳多少个单元格（最长下降子序列）

-----------------------------------

下面是最长上升子序列的代码

memset(q,0x3f,sizeof q);q[0]=-inf;int maxx=0;
for(int i=0;i<n;i++){int pos=lower_bound(q,q+n,a[i])-q-1;q[pos+1]=a[i];maxx=max(maxx,pos+1);}

最长下降子序列代码

for (int i = 0; i < n; i++) {cin >> v[i];}dp.push_back(v[0]);for (int i = 1; i < n; i++) {if (v[i] < dp.back()) dp.push_back(v[i]);else {int l = 0, r = dp.size()-1;while (l < r) {int m = l + (r - l) / 2;if (v[i] < dp[m])l = m + 1;else r = m;}dp[l] = v[i];}

-------------------

经过每个点4个方向的预处理

#include<iostream>
#include<algorithm>
#include<numeric>//accumulate(be,en,0)
#include<cstring>//rfind("string"),s.find(string,begin)!=s.npos,find_first _of(),find_last_of()
#include<string>//to_string(value),s.substr(int begin, int length);
#include<cstdio>
#include<cmath>
#include<vector>//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end()),vector<int>().swap(at[mx])
#include<queue>//priority_queue(big)  /priority_queue<int, vector<int>, greater<int>> q(small)
#include<stack>
//#include<map>//unordered_map
#include<set>//iterator,insert(),erase(),lower(>=)/upper_bound(>)(value)/find()return end()
#include<unordered_map>
#include<unordered_set>
#include<bitset>//size,count(size of 1),reset(to 0),any(have 1?)
//#include<ext/pb_ds/assoc_container.hpp>//gp_hash_table
//#include<ext/pb_ds/hash_policy.hpp>
//using namespace __gnu_pbds;
#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 5, mod = 1e9 + 7;
signed main() {ios_base::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {int n, m;cin >> n >> m;vector<vector<int>>q(n + 5, vector<int>(m + 5));//存储原来矩阵vector<vector<int>>q2(n + 5, vector<int>(m + 5));//存储第一次上下移动的矩阵的最大值vector<vector<int>>q1(n + 5, vector<int>(m + 5));//存储第一次左右移动的矩阵的最大值vector<vector<int>>q3(n + 5, vector<int>(m + 5));//存储第二次上下移动的矩阵的最大值vector<vector<int>>q4(n + 5, vector<int>(m + 5));//存储第二次左右移动的矩阵的最大值for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> q[i][j];}}vector<int>w, tmp(m + 5), tmp2(n + 5);for (int i = 1; i < m + 5; i++) tmp[i] = inf;for (int i = 1; i < n + 5; i++) tmp2[i] = inf;for (int i = 1; i <= n; i++) {//求每一行从左到右的最长上升子序列w = tmp;w[0] = -inf;for (int j = 1; j <= m; j++) {int pos = lower_bound(w.begin(), w.end(), q[i][j]) - w.begin() - 1;w[pos + 1] = q[i][j];q1[i][j] = pos + 1;}}for (int i = 1; i <= n; i++) {w = tmp;w[0] = -inf;for (int j = m; j >= 1; j--) {int pos = lower_bound(w.begin(), w.end(), q[i][j]) - w.begin() - 1;w[pos + 1] = q[i][j];q1[i][j] = max(q1[i][j], pos + 1);}}for (int i = 1; i <= m; i++) {//每一行从右到左 的上升子序列(下面同理)w = tmp2;w[0] = -inf;for (int j = 1; j <= n; j++) {int pos = lower_bound(w.begin(), w.end(), q[j][i]) - w.begin() - 1;w[pos + 1] = q[j][i];q2[j][i] = pos + 1;}}for (int i = 1; i <= m; i++) {w = tmp2;w[0] = -inf;for (int j = n; j >= 1; j--) {int pos = lower_bound(w.begin(), w.end(), q[j][i]) - w.begin() - 1;w[pos + 1] = q[j][i];q2[j][i] = max(q2[j][i], pos + 1);}}//------------------------for (int i = 1; i <= n; i++) {//每一行从左到右的下降子序列q3[i][1] = 1;vector<int>dp;dp.push_back(q[i][1]);for (int j = 2; j <= m; j++) {if (q[i][j] < dp.back()) {dp.push_back(q[i][j]); q3[i][j] = dp.size();}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[i][j] < dp[mid]) l = mid + 1;else r = mid;}q3[i][j] = l + 1;dp[l] = q[i][j];}}}for (int i = 1; i <= n; i++) {vector<int>dp;dp.push_back(q[i][m]);for (int j = m - 1; j >= 1; j--) {if (q[i][j] < dp.back()) {dp.push_back(q[i][j]); q3[i][j] = max(q3[i][j], (int)dp.size());}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[i][j] < dp[mid]) l = mid + 1;else r = mid;}q3[i][j] = max(q3[i][j], l + 1);dp[l] = q[i][j];}}}for (int i = 1; i <= m; i++) {q4[1][i] = 1;vector<int>dp;dp.push_back(q[1][i]);for (int j = 2; j <= n; j++) {if (q[j][i] < dp.back()) {dp.push_back(q[j][i]); q4[j][i] = dp.size();}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[j][i] < dp[mid]) l = mid + 1;else r = mid;}q4[j][i] = l + 1;dp[l] = q[j][i];}}}for (int i = 1; i <= m; i++) {vector<int>dp;dp.push_back(q[n][i]);for (int j = n - 1; j >= 1; j--) {if (q[j][i] < dp.back()) {dp.push_back(q[j][i]); q4[j][i] = max(q4[j][i], (int)dp.size());}else {int l = 0, r = dp.size() - 1;while (l < r) {int mid = l + (r - l) / 2;if (q[j][i] < dp[mid]) l = mid + 1;else r = mid;}q4[j][i] = max(q4[j][i], l + 1);dp[l] = q[j][i];}}}int maxx = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {maxx = max({ maxx,q1[i][j] + q4[i][j],q2[i][j] + q3[i][j] });
//第一次上下+第二次左右，第一次左右+第二次上下}}cout << maxx - 1 << '\n';}
}