對rock的一些思考與問題
題目
寶庫通道（Rock）
探寶的旅程仍然繼續(xù)中，由于你的幫助，小可可成功點燃了燈陣，避過了許多致命的陷阱，終于來到了宮殿的正廳中。大廳的地面是由一塊塊大小一致的正方形石塊組成的，這些石塊分為黑、白兩色，組成了一個m*n的矩形，在其中一個石塊的下面就是通往藏寶庫的通道。小可可不可能一個一個石塊的嘗試，因為有些石塊安裝了機關(guān)，一碰就會觸發(fā)，整個宮殿也隨之倒塌。根據(jù)藏寶圖記載，通道在某一特定的區(qū)域中，這個區(qū)域是一個由數(shù)個石塊組成的面積不為0的小矩形，它的四條邊與大廳地面的邊平行。如果對整個大廳地面任意劃分矩形，那么在所有矩形中，這個區(qū)域的黑色石塊數(shù)目減去白色石塊數(shù)目所得的差是最大的。
小可可希望和你分工，由他來選擇區(qū)域，你來計算黑、白兩色石塊的數(shù)目差S。這樣就能快速而準確的確認通道所在的區(qū)域。藏寶圖上說這個區(qū)域中的石塊都沒有安裝機關(guān)，只要確定了區(qū)域，就一定能找到通道。寶藏就在眼前了，加油吧！
（假設(shè)用1表示黑色石塊，用0表示白色石塊）
輸入：輸入文件的第一行為兩個整數(shù)m,n (1<=m,n<=400).
以下m行，每行n個字符，每個字符都是0或1。
輸出：輸出文件僅一個數(shù)，表示所有可能的區(qū)域中S值（見前文描述）最大的一個，輸出這個值即可。
樣例：
輸入：
3 4
1011
1111
1111
輸出：
10
四重循環(huán)：
四重循環(huán)比較簡單，即求
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)
三重循環(huán)
三重循環(huán)使用dp 但是我用了三位數(shù)組可能超空間。
提問
1． 我用三重循環(huán)時用的是“豎窮舉，橫dp”，我想要達到“橫豎都要dp”，怎么辦？
2． 我的程序在下面
三重循環(huán)
#include
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;jmaxj) 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>tmp;
a[i][j]=(tmp=='0')?-1:1;
}
for (int x=0;x
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>a;
palace[i][j]=a-'0';
if (palace[i][j]==0) palace[i][j]=-1;
}
for (int i=0;imax) max=now;
}
fout<
對rock的一些思考與問題
題目
寶庫通道（Rock）
探寶的旅程仍然繼續(xù)中，由于你的幫助，小可可成功點燃了燈陣，避過了許多致命的陷阱，終于來到了宮殿的正廳中。大廳的地面是由一塊塊大小一致的正方形石塊組成的，這些石塊分為黑、白兩色，組成了一個m*n的矩形，在其中一個石塊的下面就是通往藏寶庫的通道。小可可不可能一個一個石塊的嘗試，因為有些石塊安裝了機關(guān)，一碰就會觸發(fā)，整個宮殿也隨之倒塌。根據(jù)藏寶圖記載，通道在某一特定的區(qū)域中，這個區(qū)域是一個由數(shù)個石塊組成的面積不為0的小矩形，它的四條邊與大廳地面的邊平行。如果對整個大廳地面任意劃分矩形，那么在所有矩形中，這個區(qū)域的黑色石塊數(shù)目減去白色石塊數(shù)目所得的差是最大的。
小可可希望和你分工，由他來選擇區(qū)域，你來計算黑、白兩色石塊的數(shù)目差S。這樣就能快速而準確的確認通道所在的區(qū)域。藏寶圖上說這個區(qū)域中的石塊都沒有安裝機關(guān)，只要確定了區(qū)域，就一定能找到通道。寶藏就在眼前了，加油吧！
（假設(shè)用1表示黑色石塊，用0表示白色石塊）
輸入：輸入文件的第一行為兩個整數(shù)m,n (1<=m,n<=400).
以下m行，每行n個字符，每個字符都是0或1。
輸出：輸出文件僅一個數(shù)，表示所有可能的區(qū)域中S值（見前文描述）最大的一個，輸出這個值即可。
樣例：
輸入：
3 4
1011
1111
1111
輸出：
10
四重循環(huán)：
四重循環(huán)比較簡單，即求
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)
三重循環(huán)
三重循環(huán)使用dp 但是我用了三位數(shù)組可能超空間。
提問
1． 我用三重循環(huán)時用的是“豎窮舉，橫dp”，我想要達到“橫豎都要dp”，怎么辦？
2． 我的程序在下面
三重循環(huán)
#include
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;jmaxj) 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>tmp;
a[i][j]=(tmp=='0')?-1:1;
}
for (int x=0;x
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>a;
palace[i][j]=a-'0';
if (palace[i][j]==0) palace[i][j]=-1;
}
for (int i=0;imax) max=now;
}
fout<