莞城微信网站建设,花蝴蝶免费视频在线观看高清版,wordpress 图文混排,莆田建设局网站http://codewaysky.sinaapp.com/problem.php?id1056 这题和奶牛浴场略有区别#xff0c;奶牛浴场只需要求出最大子矩形#xff0c;而这题要求的是最大权重子矩形#xff0c;不一定要最大的面积#xff0c;但要最大的权重和 思路是先求出每个最大子矩形#xff0c;然后求出… http://codewaysky.sinaapp.com/problem.php?id1056 这题和奶牛浴场略有区别奶牛浴场只需要求出最大子矩形而这题要求的是最大权重子矩形不一定要最大的面积但要最大的权重和 思路是先求出每个最大子矩形然后求出每个矩形的左上点和右下点然后用二维数转数组进行求和保存最优解 View Code 1 #includeiostream2 #includestring3 #includealgorithm4 #includestdio.h5 #includememory.h6 using namespace std;7 8 int sum[1010][1010];9 int v[1010][1010];10 int l[1010],r[1010],h[1010];11 int n,m;12 13 //****************************//树状数组14 int lowbit(int x)15 {16 return x-x;17 }18 19 void add(int x,int y,int w)20 {21 int i,j;22 for(ix;in;ilowbit(i))23 {24 for(jy;jm;jlowbit(j))25 sum[i][j]w;26 }27 }28 29 int get_sum(int x,int y)30 {31 int i,j,ans0;32 for(ix;i0;i-lowbit(i))33 {34 for(jy;j0;j-lowbit(j))35 {36 anssum[i][j];37 }38 }39 return ans;40 }41 //*****************************//42 43 int find(int x1,int y1,int x2,int y2)44 {45 return get_sum(x2,y2)-get_sum(x1-1,y2)-get_sum(x2,y1-1)get_sum(x1-1,y1-1);46 }47 48 int main()49 {50 int i,j,w,x1,x2,y1,y2;51 freopen(D:\\in.txt,r,stdin);52 while(scanf(%d%d,n,m)2)53 {54 memset(sum,0,sizeof(sum));55 memset(v,0,sizeof(v));56 for(i1;in;i)57 {58 for(j1;jm;j)59 {60 scanf(%d,w);61 if(!w)62 v[i][j]1;63 else64 add(i,j,w);65 }66 }67 for(i0;im;i)68 {69 h[i]0;l[i]1;r[i]m;70 }71 int lm,rm,ans0,temp;72 for(i1;in;i)73 {74 lm1;75 for(j1;jm;j)76 {77 if(!v[i][j])78 {79 h[j];80 if(lml[j])81 l[j]lm;82 }83 else84 {85 h[j]0; //边界不能有洞所以障碍点高度是0而不是186 l[j]1;87 r[j]m;88 lmj1; //由于边界不能有洞所以加189 }90 }91 rmm;92 for(jm;j0;j--)93 {94 if(r[j]rm)95 r[j]rm;96 if(h[j])97 {98 y1l[j];y2r[j]; //处理出举行的左上点和右下点99 x1i-h[j]1;x2i;
100 tempfind(x1,y1,x2,y2); //利用二维数转数组进行求和
101 if(tempans)
102 anstemp;
103 }
104 else
105 rmj-1; //同理减一
106 }
107 }
108 printf(%d\n,ans);
109 }
110 return 0;
111 } 转载于:https://www.cnblogs.com/ka200812/archive/2012/09/30/2709217.html
