﻿<?xml version="1.0" encoding="utf-8" standalone="yes"?><rss version="2.0" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/" xmlns:wfw="http://wellformedweb.org/CommentAPI/" xmlns:slash="http://purl.org/rss/1.0/modules/slash/"><channel><title>C++博客-C++天空</title><link>http://www.cppblog.com/cpp-stu2/</link><description>cpp_stu2's Land</description><language>zh-cn</language><lastBuildDate>Thu, 09 Apr 2026 11:12:41 GMT</lastBuildDate><pubDate>Thu, 09 Apr 2026 11:12:41 GMT</pubDate><ttl>60</ttl><item><title>关于rock的一些思考</title><link>http://www.cppblog.com/cpp-stu2/archive/2007/06/30/27266.html</link><dc:creator>姜雨生</dc:creator><author>姜雨生</author><pubDate>Sat, 30 Jun 2007 03:00:00 GMT</pubDate><guid>http://www.cppblog.com/cpp-stu2/archive/2007/06/30/27266.html</guid><wfw:comment>http://www.cppblog.com/cpp-stu2/comments/27266.html</wfw:comment><comments>http://www.cppblog.com/cpp-stu2/archive/2007/06/30/27266.html#Feedback</comments><slash:comments>0</slash:comments><wfw:commentRss>http://www.cppblog.com/cpp-stu2/comments/commentRss/27266.html</wfw:commentRss><trackback:ping>http://www.cppblog.com/cpp-stu2/services/trackbacks/27266.html</trackback:ping><description><![CDATA[
对rock的一些思考与问题
题目
宝库通道（Rock）
探宝的旅程仍然继续中，由于你的帮助，小可可成功点燃了灯阵，避过了许多致命的陷阱，终于来到了宫殿的正厅中。大厅的地面是由一块块大小一致的正方形石块组成的，这些石块分为黑、白两色，组成了一个m*n的矩形，在其中一个石块的下面就是通往藏宝库的通道。小可可不可能一个一个石块的尝试，因为有些石块安装了机关，一碰就会触发，整个宫殿也随之倒塌。根据藏宝图记载，通道在某一特定的区域中，这个区域是一个由数个石块组成的面积不为0的小矩形，它的四条边与大厅地面的边平行。如果对整个大厅地面任意划分矩形，那么在所有矩形中，这个区域的黑色石块数目减去白色石块数目所得的差是最大的。
小可可希望和你分工，由他来选择区域，你来计算黑、白两色石块的数目差S。这样就能快速而准确的确认通道所在的区域。藏宝图上说这个区域中的石块都没有安装机关，只要确定了区域，就一定能找到通道。宝藏就在眼前了，加油吧！
（假设用1表示黑色石块，用0表示白色石块）

输入：输入文件的第一行为两个整数m,n (1<=m,n<=400).
以下m行，每行n个字符，每个字符都是0或1。

输出：输出文件仅一个数，表示所有可能的区域中S值（见前文描述）最大的一个，输出这个值即可。

样例：
输入：
3 4
1011
1111
1111
输出：
10
四重循环：
四重循环比较简单，即求
area(x1,x2,y1,y2)=area(0,0,x2,y2)-area(0,0,x1,y2)-area(0,0, x2,y1)+area(0,0, x1, y2)

三重循环
    三重循环使用dp 但是我用了三位数组可能超空间。
提问
1．	我用三重循环时用的是&#8220;竖穷举，横dp&#8221;，我想要达到&#8220;横竖都要dp&#8221;，怎么办？
2．	我的程序在下面
         三重循环
#include<fstream>
using namespace std;
ifstream fin ("rock.in");
ofstream fout ("rock.out");
int m,n;
int maxx=0;
int a[400][400];
int b[400][400][400];
void ask1(int x,int y,int lng)
{
	int sum=0;
	for (int i=y;i<=lng;i++)
	    sum+=a[x][i];
    b[x][y][lng]=sum;
}
void ask2(int x,int y,int lng)
{
	int now=0;
	int maxj=0;
	for (int j=x;j<m;j++)
	{
		now+=b[j][y][lng];
		if (now>maxj) maxj=now;
		else if (now<0) now=0;
	}
	if (maxj>maxx) maxx=maxj;
}
int main (void)
{
	fin>>m>>n;
	char tmp;
	for (int i=0;i<m;i++)
        for (int j=0;j<n;j++)
        {
		    fin>>tmp;
			a[i][j]=(tmp=='0')?-1:1;
        }
	for (int x=0;x<m;x++)
        for (int y=0;y<n;y++)
		    for (int lng=y;lng<n;lng++)
                ask1(x,y,lng);
	for (int x=0;x<m;x++)
        for (int y=0;y<n;y++)
		    for (int lng=y;lng<n;lng++)
                ask2(x,y,lng);
	fout<<maxx<<endl;
	return 0;
}
四重循环
#include<fstream>
using namespace std;
ifstream fin ("rock.in");
ofstream fout ("rock.out");
int palace[400][400]={0},b[400][400]={0};
int main (void)
{
    long max=0;
	int N,M;
	fin>>N>>M;
	for (int i=0;i<N;i++)
		for (int j=0;j<M;j++)
	    {
		    char a;
			fin>>a;
		    palace[i][j]=a-'0';
			if (palace[i][j]==0) palace[i][j]=-1;
	    }
	for (int i=0;i<N;i++)
		for (int j=0;j<M;j++)
            for (int from1=0;from1<=i;from1++)
		        for (int from2=0;from2<=j;from2++)
                    b[i][j]+=palace[from1][from2];
	for (int i=0;i<N;i++)
        for (int j=0;j<M;j++)
            for (int x=i;x<N;x++)
		        for (int y=j;y<M;y++)
		        {
		            long now=0;
					now=b[x][y]-b[x][j-1]-b[i-1][y]+b[i-1][j-1];
					if (now>max) max=now;
		        }
	fout<<max<<endl;
	return 0;
}

 <img src ="http://www.cppblog.com/cpp-stu2/aggbug/27266.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.cppblog.com/cpp-stu2/" target="_blank">姜雨生</a> 2007-06-30 11:00 <a href="http://www.cppblog.com/cpp-stu2/archive/2007/06/30/27266.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item></channel></rss>