长沙电商网站开发,兼职做国外网站钻前,无人区在线影院免费高清,怎样做自己的 优惠卷网站链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
思路#xff1a;
直接枚举这个图中的拐点
这个拐点是经过左右平移到上下平移或者上下平移到左右平移
假设这个点事左到右后然后再从下到上
左到右就相当于走了个最长上升子序列#xff0…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
思路
直接枚举这个图中的拐点
这个拐点是经过左右平移到上下平移或者上下平移到左右平移
假设这个点事左到右后然后再从下到上
左到右就相当于走了个最长上升子序列然后再从下到上
从下到上的过程你可以反过来看就是从上走到下就相当从上到下走了个最长下降子序列
然后最长上升/下降子序列可以用dp二分来求
按题解的话来说就是 预处理出对于每个单元格四个方向上最多跳多少个单元格可以跳到当前单元格(最长上升子序列)以及从当前单元格跳出最多能跳多少个单元格最长下降子序列
-----------------------------------
下面是最长上升子序列的代码
memset(q,0x3f,sizeof q);q[0]-inf;int maxx0;
for(int i0;in;i){int poslower_bound(q,qn,a[i])-q-1;q[pos1]a[i];maxxmax(maxx,pos1);}
最长下降子序列代码
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个方向的预处理
#includeiostream
#includealgorithm
#includenumeric//accumulate(be,en,0)
#includecstring//rfind(string),s.find(string,begin)!s.npos,find_first _of(),find_last_of()
#includestring//to_string(value),s.substr(int begin, int length);
#includecstdio
#includecmath
#includevector//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end()),vectorint().swap(at[mx])
#includequeue//priority_queue(big) /priority_queueint, vectorint, greaterint q(small)
#includestack
//#includemap//unordered_map
#includeset//iterator,insert(),erase(),lower()/upper_bound()(value)/find()return end()
#includeunordered_map
#includeunordered_set
#includebitset//size,count(size of 1),reset(to 0),any(have 1?)
//#includeext/pb_ds/assoc_container.hpp//gp_hash_table
//#includeext/pb_ds/hash_policy.hpp
//using namespace __gnu_pbds;
#define int long long//__int128 2^127-1(GCC)
#define PII pairint,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;vectorvectorintq(n 5, vectorint(m 5));//存储原来矩阵vectorvectorintq2(n 5, vectorint(m 5));//存储第一次上下移动的矩阵的最大值vectorvectorintq1(n 5, vectorint(m 5));//存储第一次左右移动的矩阵的最大值vectorvectorintq3(n 5, vectorint(m 5));//存储第二次上下移动的矩阵的最大值vectorvectorintq4(n 5, vectorint(m 5));//存储第二次左右移动的矩阵的最大值for (int i 1; i n; i) {for (int j 1; j m; j) {cin q[i][j];}}vectorintw, 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;vectorintdp;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) {vectorintdp;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;vectorintdp;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) {vectorintdp;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;}
}
