[ZJOI2007]棋盘制作 悬线法dp 求限制下的最大子矩阵

时间:2022-01-28 00:38:14

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 now=;register char c=getchar();for(;!isdigit(c);c=getchar());
for(;isdigit(c);now=now*+c-'',c=getchar());return now;}
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;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 i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
const double eps = 1e-;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
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 = ; i <= N ; i ++){
for(int j = ; j <= M ; j ++){
Sca(MAP[i][j]);
Left[i][j] = Right[i][j] = j;
up[i][j] = ;
}
}
for(int i = ; i <= N ; i ++){
for(int j = ; j <= M ; j ++){
if(MAP[i][j] != MAP[i][j - ]){
Left[i][j] = Left[i][j - ];
}
}
for(int j = M - ; j >= ; j --){
if(MAP[i][j] != MAP[i][j + ]){
Right[i][j] = Right[i][j + ];
}
}
}
int ans1 = ,ans2 = ;
for(int i = ; i <= N ; i ++){
for(int j = ; j <= M ; j ++){
if(i > && MAP[i][j] != MAP[i - ][j]){
Left[i][j] = max(Left[i][j],Left[i - ][j]);
Right[i][j] = min(Right[i][j],Right[i - ][j]);
up[i][j] = up[i - ][j] + ;
}
int a = Right[i][j] - Left[i][j] + ;
int b = min(a,up[i][j]);
ans1 = max(ans1,b * b);
ans2 = max(ans2,a * up[i][j]);
}
}
Pri(ans1);
Pri(ans2);
return ;
}

[ZJOI2007]棋盘制作 悬线法dp 求限制下的最大子矩阵的更多相关文章

  1. P1169 &lbrack;ZJOI2007&rsqb;棋盘制作 &amp&semi;&amp&semi; 悬线法

    P1169 [ZJOI2007]棋盘制作 给出一个 \(N * M\) 的 \(01\) 矩阵, 求最大的正方形和最大的矩形交错子矩阵 \(n , m \leq 2000\) 悬线法 悬线法可以求出给 ...

  2. BZOJ 1057&colon; &lbrack;ZJOI2007&rsqb;棋盘制作 悬线法求最大子矩阵&plus;dp

    1057: [ZJOI2007]棋盘制作 Description 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源于易经的思想,棋盘是一个8*8大小的黑 ...

  3. P1169 &lbrack;ZJOI2007&rsqb;棋盘制作&lbrack;悬线法&sol;二维dp&rsqb;

    题目描述 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源于易经的思想,棋盘是一个8 \times 88×8大小的黑白相间的方阵,对应八八六十四卦,黑白 ...

  4. 洛谷P1169 &lbrack;ZJOI2007&rsqb;棋盘制作 悬线法 动态规划

    P1169 [ZJOI2007]棋盘制作 (逼着自己做DP 题意: 给定一个包含0,1的矩阵,求出一个面积最大的正方形矩阵和长方形矩阵,要求矩阵中相邻两个的值不同. 思路: 悬线法. 用途: 解决给定 ...

  5. P1169 &lbrack;ZJOI2007&rsqb;棋盘制作——悬线法

    ---恢复内容开始--- 给你一个矩阵,选出最大的棋盘,棋盘的要求是黑白相间(01不能相邻),求出最大的正方形和矩形棋盘的面积: 数据n,m<=2000; 这个一看就可能是n2DP,但是写不出. ...

  6. P1169 &lbrack;ZJOI2007&rsqb;棋盘制作 悬线法or单调栈

    思路:悬线法\(or\)单调栈 提交:2次 错因:正方形面积取错了\(QwQ\) 题解: 悬线法 讲解:王知昆\(dalao\)的\(PPT\) 详见代码: #include<cstdio&gt ...

  7. 【ZJOI2007】棋盘制作 - 悬线法

    题目描述 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源于易经的思想,棋盘是一个 \(8 \times 8\) 大小的黑白相间的方阵,对应八八六十四卦 ...

  8. luogu 1169 &lbrack;ZJOI2007&rsqb;棋盘制作 悬线dp

    悬线法,虽然得不到局部最优解,但是一定能得到全局最优解的算法,十分神奇~ #include <cstdio> #include <algorithm> #define N 20 ...

  9. 【BZOJ-3039&amp&semi;1057】玉蟾宫&amp&semi;棋盘制作 悬线法

    3039: 玉蟾宫 Time Limit: 2 Sec  Memory Limit: 128 MBSubmit: 753  Solved: 444[Submit][Status][Discuss] D ...

随机推荐

  1. SB Admin 2 学习笔记1

    需要掌握能够搭建起一个 dashboard 的能力, 因为很少有运维开发团队有专职的前端, bootstrap 也要讲个基本法. SB Admin 2, 一个免费的 bootstrap theme, ...

  2. Yii2的深入学习--事件Event

    我们先来看下事件在 Yii2 中的使用,如下内容摘自 Yii2中文文档 事件可以将自定义代码“注入”到现有代码中的特定执行点.附加自定义代码到某个事件,当这个事件被触发时,这些代码就会自动执行.例如, ...

  3. BZOJ4522&colon; &lbrack;Cqoi2016&rsqb;密钥破解

    pollard's rho模板题. 调参调到160ms无能为力了,应该是写法问题,不玩了. #include<bits/stdc++.h> using namespace std; typ ...

  4. Sklearn库例子1:Sklearn库中AdaBoost和Decision Tree运行结果的比较

    DisCrete Versus Real AdaBoost 关于Discrete 和Real AdaBoost 可以参考博客:http://www.cnblogs.com/jcchen1987/p/4 ...

  5. Coursera获取中文字幕(如果有的话)

    字幕的格式是  https://class.coursera.org/${课程代号}/lecture/subtitles?q=${视频编号}_zh-cn 例如 https://class.course ...

  6. 算法:求 Huffuman树 构造费用

    问题背景:            Huffman树在编码中有着广泛的应用.在这里,我们只关心Huffman树的构造过程.            给出一列数{pi}={p0, p1, …, pn-1}, ...

  7. cocos2d 缓存池 对象的再利用

    1.简单的叙述说明池 例如,我们知道,游戏的游戏类型跑酷,游戏元素都在不断重复.游戏的内容将继续从屏幕右侧的创建,当元件在屏幕的左侧的,将消失.假设不变new 对象.release 对象 性能影响.怎 ...

  8. 背包DP入门小笔记01背包

    FJUT OJ 2347 http://59.77.139.92/Problem.jsp?pid=2347 采药 TimeLimit:1000MS  MemoryLimit:128MB 64-bit ...

  9. SQL介绍

    SQL,即structured query language,结构化查询语言,是一种对关系型数据库中的数据进行管理和操作的语言方法,SQL包括6个部分 DQL:数据查询语言,最常用的为select,其 ...

  10. JAVAWEB开发之HttpServletResponse和HttpServletRequest详解&lpar;下&rpar;(各种乱码、验证码、重定向和转发)

    HttpServletRequest获取请求头信息  (1)获取客户机请求头 String getHeader(String name) Enumeration<String> getHe ...