首页 > 代码库 > hdu--1505--稍微特别的子矩阵求和
hdu--1505--稍微特别的子矩阵求和
这题 是蛮特别的..
虽然可以将R F转换为 0 1然后求最大子矩阵和 但是这个矩阵中 不能有0 即这个矩阵的元素都是1即F
这题 一开始不会做啊=-= 看了discuss里面的人用了 left 和 right数组 还是一知半解 白痴啊=-=
我把我的理解和porker讲了下 他纠正了我的错误... ------touch me
我这边将left 和 next 和 height数组简单讲下我的理解 因为我发现 基本上所有人都是没有给出解释的。。。
假如我们现在要操作第 X 行 的 第 Y 列 那么 left[ Y ]就是在Y列左边 能取到的最小列的编号Z使得从Z到Y的列的height都是>=Y
那么right[ Y ]就是同理了 一个是在右边 一个是在左边罢了
height[ Y ]就是在第X行时 第Y列及上门1-X行包含第Y列的连续free space有几个 这边当时有个情况一下子没理解 假如第X行的情况是 F R F F R F那么它对应的height[]值就是1 0 1 2 0 1因为如果是R 就会判断将height[ Y ]重置为0
那么 一个包含第 Y 列的矩阵的面积就是 height[ Y ] * ( RIGHT[ Y ] - LEFT[ Y ] + 1 )
这题 的核心代码 我觉得应该就是---前面一个对于 h l r三个数组的预处理
1 memset( height , 0 , sizeof(height) );2 for( int i = 1 ; i<=m ; i++ )3 {4 Left[i] = i;5 Right[i] = i;6 }
1 for( int k = 2 ; k<=m ; k++ ) 2 { 3 if( h[ Left[k]-1 ] >= h[k] )//其实 完全可以写成 if( h[ k-1 ] >= h[ k ] ){ left[ k ] = left[ k-1 ] ;;关于right数组 下同 至于代码那边就懒得去改了 4 { 5 Left[k] = Left[ Left[k]-1 ]; 6 } 7 } 8 9 for( int q = m-1 ; q>=1 ; q-- ) 10 {11 if( h[ Right[q]+1 ] >= h[q] )12 {13 Right[q] = Right[ Right[q]+1 ];14 }15 }
我发现 很多人对于这个left right数组进行求解的时候 都是while循环 就像下面这样
1 h[0] = h[m+1] = -1; 2 3 for( int k = 2 ; k<=m ; k++ ) 4 { 5 while( h[ Left[k]-1 ] >= h[k] ) 6 { 7 Left[k] = Left[ Left[k]-1 ]; 8 } 9 }10 11 for( int q = m-1 ; q>=1 ; q-- ) 12 {13 while( h[ Right[q]+1 ] >= h[q] )14 {15 Right[q] = Right[ Right[q]+1 ];16 }17 }
如果你是用while循环 那么一定不能忘了这个边界处理 h[0] h[m+1] 因为循环可能会存在情况到边界判断
但其实完全没必要的 因为我们的left right数组在计算的时候 我们都运用了前面计算得到的结果 直接会跳转到最终的情况、
-----------------------------
上面是O(n*m)的解法 当然 更普通的解法是O(n^3)的解法 我在1081里就是这样做的 但是当时的数据是只有100 而这里是1000
porker提醒我的用这个方法解下看 我自己当时因为觉得O(n^3)怎么判断这个和最大的矩阵不含有Ri呢？ 其实很简单 只要将每个R出现的地方 都设一个负值 使如果含有该R的子矩阵的和都是负数 就可以了 这里的负值 不能设太小 因为这样可能会存在数值溢出 因为如果使用64位int计算的话 速度会更慢一些 相比于使用32位int 这里已经存在tle的风险了 尽量节约时间
but -------------还是 tle了 =-= 谁看到这边 如果使用了我这种思想AC的 不妨留下你的评论与方法。。
--------更加难想到的是用stack维护一个单调窗口吧 我还没很好掌握它 先不说了
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 const int inf = -1100000; 6 const int size = 1010; 7 int matrix[size][size]; 8 9 int main()10 {11 cin.sync_with_stdio(false);12 int n , m , t , ans , sum , temp , num;13 char ch;14 while( cin >> t )15 {16 while( t-- )17 {18 ans = 0;19 cin >> n >> m;20 memset( matrix , 0 , (n+3)*(m+3)*sizeof(int) );21 for( int i = 1 ; i<=n ; i++ )22 {23 for( int j = 1 ; j<=m ; j++ )24 {25 cin >> ch;26 if( ch==‘F‘ )27 num = 1;28 else29 num = inf;30 matrix[i][j] = matrix[i-1][j] + num;31 }32 }33 for( int i = 1 ; i<=n ; i++ )34 {35 for( int j = i ; j<=n ; j++ )36 {37 sum = 0;38 for( int k = 1 ; k<=m ; k++ )39 {40 temp = matrix[j][k] - matrix[i-1][k];41 sum += temp;42 if( sum>ans )43 ans = sum;44 if( sum<0 )45 sum = 0;46 }47 }48 }49 cout << 3*ans << endl;50 }51 }52 return 0;53 }
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 1010; 7 int Left[size]; 8 int Right[size]; 9 int h[size];10 11 int main()12 {13 cin.sync_with_stdio(false);14 int n , m , t , ans;15 char ch;16 while( cin>>t )17 {18 while( t-- )19 {20 memset( h , 0 , sizeof(h) );21 ans = 0;22 cin >> n >> m;23 for( int i = 1 ; i<=n ; i++ )24 {25 for( int j = 1 ; j<=m ; j++ )26 {27 cin >> ch;28 if( ch ==‘F‘ )29 h[j] ++;30 else31 h[j] = 0;32 Left[j] = Right[j] = j;33 }34 //h[0] = h[m+1] = -1;35 for( int k = 2 ; k<=m ; k++ ) 36 {37 if( h[ Left[k]-1 ] >= h[k] )38 {39 Left[k] = Left[ Left[k]-1 ];40 }41 }42 for( int q = m-1 ; q>=1 ; q-- ) 43 {44 if( h[ Right[q]+1 ] >= h[q] )45 {46 Right[q] = Right[ Right[q]+1 ];47 }48 }49 for( int r = 1 ; r<=m ; r++ )50 {51 ans = max( ans , h[r] * ( Right[r] - Left[r] + 1 ) );52 }53 }54 cout << 3*ans << endl;55 }56 }57 return 0;58 }
today:
crave you name on hearts and not on marbles