链接：https://www.luogu.com.cn/problem/P1434
题目：
思路：找每个点的小于链的长度，存在lenless里；找每个点的大于链，存在于lengreat中。
然后两个相加，排序，选择最大的那个数字。注意这里长度要加1，因为没有加上自己的（初始数据设置成0）！
（按理说其实每个都少了1，所以应当全加1再排序，但是改变顺序不影响结果）
注意：这是一维数组为了便于排序，也就是numlst[i][j]转换为：i*c+j
额，怎么说呢，动态规划感觉确实像记忆化搜索（
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;
const int N = 110;
int r, c;
int numlst[N][N];
int lenless[N*N];
int lengreat[N * N];
int lenth[N * N];
int del[][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int dfs(int i, int j,bool a)
{
//找小于链的
int ans = 0;
if (!a)
{
if (lenless[i * c + j] != 0)
return lenless[i * c + j];
for (int ii = 0; ii < 4; ii++)
{
int di = i + del[ii][0], dj = j + del[ii][1];
if (di >= 0 and di < r and dj >= 0 and dj < c)
{
if (numlst[di][dj] < numlst[i][j])
ans = max(ans, dfs(di, dj, 0) + 1);
}
}
return lenless[i * c + j] = ans;
}
else
{
if (lengreat[i * c + j] != 0)
return lengreat[i * c + j];
for (int ii = 0; ii < 4; ii++)
{
int di = i + del[ii][0], dj = j + del[ii][1];
if (di >= 0 and di < r and dj >= 0 and dj < c)
{
if (numlst[di][dj] > numlst[i][j])
ans =max(ans, dfs(di, dj, 1) + 1);//这里记录多方向的最大长度，也就是下一条链的长度+1
}
}
return lengreat[i * c + j] = ans;
}
}
int main()
{
cin >> r >> c;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
cin >> numlst[i][j];
memset(lenless, 0, sizeof(lenless));
memset(lengreat, 0, sizeof(lengreat));
memset(lenth, 0, sizeof(lenth));
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (lenless[i*c+j] == 0)
{
dfs(i, j , 0);
}
if (lengreat[i * c + j] == 0)
dfs(i, j, 1);
}
}
for (int i = 0; i < c * r; i++)lenth[i] = lenless[i] + lengreat[i];
sort(lenth, lenth + c * r);
cout << lenth[c * r - 1] + 1 ;
return 0;
}