w****x
发帖数: 2483 | 1 1. 给多台机器和一个很大的矩阵，里面有0有1，让查找里面最大的1组，任
何形状的都行，怎么设计并行计算的办法
2. 一个M*N的01矩阵找最大的0矩形，不是正方形啊 |
l*******b
发帖数: 2586 | 2 第二个不是传说中的max rectangle吗，据说化成historgram解，没想好怎么写 |
w****x
发帖数: 2483 | 3 max rectangle做了个O(n^3)的解法， histogram那个我是不指望了
const int M = 5;
int GetMaxRect(bool A[M][M])
{
int rec[M][M];
for (int j = 0; j < M; j++)
{
for (int i = 0; i < M; i++)
{
if (A[i][j])
rec[i][j] = 0;
else
rec[i][j] = i == 0 ? 1 : 1 + rec[i-1][j];
}
}
int nMax = 0;
for (int i = M-1; i >= 0; i--)
{
for (int j = i; j >= 0; j--)
{
int nLen = 0;
int nBeg = -1;
for (int k = 0; k < M; k++)
{
if (rec[i][k] != 0 && rec[j][k] != 0 && rec[i][k] - rec[j][k
] == i - j) //missing rec[j][k] != 0
{
if (nBeg < 0)
nBeg = k;
nLen = max(nLen, k - nBeg + 1);
}
else nBeg = -1;
}
nMax = max(nMax, nLen*(i-j+1));
}
}
return nMax;
} |
b*********h
发帖数: 103 | 4 2. 如果楼主对 IOI 集训队论文感兴趣，03 年王知昆谈了这个话题 讲的挺好的
【在 w****x 的大作中提到】
: 1. 给多台机器和一个很大的矩阵，里面有0有1，让查找里面最大的1组，任
: 何形状的都行，怎么设计并行计算的办法
: 2. 一个M*N的01矩阵找最大的0矩形，不是正方形啊
|
b*****u
发帖数: 648 | 5 1. 分块BFS？ 在每一块里记下该块最大cluster和边界上的所有clusters，然后把各块
在边
界上碰上的cluster相加，取全局最大
2.按照这个帖子说的来
http://homeofcox-cs.blogspot.com/2010/04/max-submatrix-problem.
最大正方形：每个格子记录该点作为右下角的最大正方形，然后从左上往右下递推
最大矩形：每个格子记录该点往右最长的空格，然后对每列进行直方图计算 |
