链接：登录—专业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];
}
-------------------文章来源：https://www.toymoban.com/news/detail-643071.html
经过每个点4个方向的预处理文章来源地址https://www.toymoban.com/news/detail-643071.html
#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';
}
}
到了这里，关于K-01BFS（2023河南萌新联赛第（五）场：郑州轻工业大学）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
