网站对于一个企业的优势,织梦本地网站建设教程,重庆景点,网络营销外包公司的评价https://www.luogu.org/problemnew/show/P1169 第一次听说到这种dp的名称叫做悬线法#xff0c;听起来好厉害 题意是求一个矩阵内的最大01交错子矩阵#xff0c;开始想的是dp[2000][2000][2]维护这个位置向上向左扩充的矩阵最大长度之后n扫一遍#xff0c;但是写起来发现并不… https://www.luogu.org/problemnew/show/P1169 第一次听说到这种dp的名称叫做悬线法听起来好厉害 题意是求一个矩阵内的最大01交错子矩阵开始想的是dp[2000][2000][2]维护这个位置向上向左扩充的矩阵最大长度之后n²扫一遍但是写起来发现并不能有效的扩充也就是状态转移方程很难写出来。 后来发现有一种奥妙重重的方法叫做悬线法把我原本向左向上扩充的过程改为记录每一个点向左向右向上的最大长度这些状态很显然可以通过扫一遍的方法求出来然后对于每一个点宽度就是l - r 1显然对于同一个合法区间内的点他的left和right是相同的。 用自上而下的方法递推出到N这一行时这个点向上扩充的最大长度之后递推即可。 悬线法对一类限制下求子矩阵的问题很好用。 #include map
#include set
#include ctime
#include cmath
#include queue
#include stack
#include vector
#include string
#include cstdio
#include cstdlib
#include cstring
#include sstream
#include iostream
#include algorithm
#include functional
using namespace std;
inline int read(){int now0;register char cgetchar();for(;!isdigit(c);cgetchar());
for(;isdigit(c);nownow*10c-0,cgetchar());return now;}
#define For(i, x, y) for(int ix;iy;i)
#define _For(i, x, y) for(int ix;iy;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf(%d, x)
#define Sca2(x,y) scanf(%d%d,x,y)
#define Sca3(x,y,z) scanf(%d%d%d,x,y,z)
#define Scl(x) scanf(%lld,x);
#define Pri(x) printf(%d\n, x)
#define Prl(x) printf(%lld\n,x);
#define CLR(u) for(int i0;iN;i)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pairint,int
#define PIL pairint,long long
#define PLL pairlong long,long long
#define pb push_back
#define fi first
#define se second
typedef vectorint VI;
const double eps 1e-9;
const int maxn 2010;
const int INF 0x3f3f3f3f;
const int mod 1e9 7;
int N,M,K;
int Left[maxn][maxn],Right[maxn][maxn],up[maxn][maxn];
int MAP[maxn][maxn];
int main()
{Sca2(N,M);for(int i 1; i N ; i ){for(int j 1; j M ; j ){Sca(MAP[i][j]);Left[i][j] Right[i][j] j;up[i][j] 1;}}for(int i 1; i N ; i ){for(int j 2; j M ; j ){if(MAP[i][j] ! MAP[i][j - 1]){Left[i][j] Left[i][j - 1];}}for(int j M - 1; j 1; j --){if(MAP[i][j] ! MAP[i][j 1]){Right[i][j] Right[i][j 1];}}}int ans1 0,ans2 0;for(int i 1; i N ; i ){for(int j 1; j M ; j ){if(i 1 MAP[i][j] ! MAP[i - 1][j]){Left[i][j] max(Left[i][j],Left[i - 1][j]);Right[i][j] min(Right[i][j],Right[i - 1][j]);up[i][j] up[i - 1][j] 1;}int a Right[i][j] - Left[i][j] 1;int b min(a,up[i][j]);ans1 max(ans1,b * b);ans2 max(ans2,a * up[i][j]);}}Pri(ans1);Pri(ans2);return 0;
} 转载于:https://www.cnblogs.com/Hugh-Locke/p/10261871.html
