异想天开

What's the true meaning of light, Could you tell me why

2维子矩阵最大和

日期:2014-05-06 16:58:43
  
最后更新日期:2014-05-06 17:04:44
描述:
给出如下n*n的矩阵:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
求出最大的子矩阵和。上例最大子矩阵为:
9 2
-4 1
-1 8
即15。
本题见杭电1081。
解答:
1.以下为一大段扯蛋的文字,可以直接查看分割线后dp方法。
这题开始想到直接用暴力搜索,因为(10^2)^4,数据量不是很大,提交之后发现是wrong answer。当时我纳闷了,擦,算法能力居然弱成这样了么。连个暴力搜索都写不出。当时想到了一句话,“一个人可以进步的很快,一群人才能走得更远”,于是考虑使用求助锦囊,发到群上,除了一阵玩笑似的嘲讽后,没有得到实际的。后来想到心流效应,于是百度了,看了一个暴力搜索的方法怎么处理输入的,恍然悟到-原来是输入问题。而我的处理输入是这样:
[code lang="cpp"]
#define N 100
int data[N][N];
void input_matrix1(int n){
string str;
stringstream ss;
int *src=(int*)data;
char ch;
for(int i=0; i<n; ++i){
std::getline(std::cin,str);
ss.str("");
//cout<<str<<endl;
ss.clear();
ss<<str;
int tmp;
for(int j=0; j<n; ++j){
ss>>tmp;
data[i][j]=tmp;
//cout<<tmp<<" ";
}
//cout<<endl;
}
}
[/code]
大概是航电上来直接矩阵的输入没有用回车,直接用一行输入的。实际中可能是这样通过管道来传递输入: [code lang="cpp"]
cat data.txt | ./test
[/code]
替换成参考1的那样,就成想到的答案-超时,然后就没有继续看那篇文章了。不知道为什么我有代码癖,贴一下暴力搜索:
[code lang="cpp"]
#include<stdio.h>
#include<sstream>
#include<iostream>
using namespace std;

#define N 100
int data[N][N];
//={{0,-2,-7,0},{9,2,-6,2},{-4,1,-4,1},{-1,8,0,-2}};
static int maxvalue=0;
void sovle_imp(int s1,int s2,int len)
{
for(int i=0; (i+s1)<=len; ++i ){
for(int j=0; (j+s2)<=len; ++j ){
int sumvalue=0;
for(int m=0; m<s1; ++m ){
for(int n=0; n<s2; ++n){
sumvalue += data[i+m][j+n];
}
}
if(sumvalue>maxvalue){
maxvalue=sumvalue;
}
//cout<<"sumvalue:"<<s1<<" "<< s2<<" "<<i<<" "<<j<<" "<<sumvalue << " maxvalue: "<<maxvalue<<end l;
}
}
}

void sovle(int len)
{
for(int i=1;i<=len;++i){
for(int j=1;j<=len;++j){
sovle_imp(i,j,len);
}
}
}

void input_matrix(int n){
int *src=(int*)data;
char ch;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
cin>>data[i][j];
//cout<<tmp<<" ";
}
//cout<<endl;
}
}

void print_matrix(int n){
for(int i=0; i<n; ++i){
cout<<endl;
for(int j=0; j<n; ++j){
cout<<data[i][j]<<" ";
}
}
cout<<endl;
}

int main()
{
int n;
char ch;
while(cin>>n){
getchar();
maxvalue=0;
input_matrix(n);
//print_matrix(n);
sovle(n);
cout<<maxvalue<<endl;
}
return 0;
}
[/code]

-------------------分隔线-------------------------------------------
2.dp方法
考虑降一维的情况,假设需要求某个数组里面,连续子串的和的最大值。这个问题可以定义这样的函数:
f(i)表示a[0]到a[i]包含a[i]的最大子串的值。
那么:
[code lang="cpp"]
f[i] = max{ a[i],a[i]+f[i-1]},即若f[i-1]<0,那么f[i]=a[i],否则f[i]=a[i]+f[i-1]。
[/code]
怎么降维呢?
定义如下函数:sum(k,i,j)表示a[k][i]+...+a[k][j]的和。(i,j)这样的值对有n^2个,n为正方形矩阵行的个数。对于一个相同的(i,j)那么就变成了一维的情况,如(0,1):
sum(0,0,1),sum(1,0,1),sum(2,0,1),...,sum(n,0,1)。
这样求出该情况的最大值,然后分别计算不同的(i,j)即可求出最大值。
code:
[code lang="cpp"]
#include<stdio.h>
#include<iostream>
using namespace std;

#define N 101
int data[N][N];
int sum[100];
int dp[100];

void input_matrix(int n){
int *src=(int*)data;
char ch;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
cin>>data[i][j];
}
}
}

int sovle_impl(int n){
dp[0]=sum[0];
int max=dp[0];
for(int i=1; i<n; ++i){
if(dp[i-1]>0){
dp[i]=dp[i-1]+sum[i];
}else{
dp[i]=sum[i];
}
if(dp[i]>max){
max=dp[i];
}
}
return max;
}

int sovle(int n){
int max=0;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
for(int u=0; u<n; ++u){
sum[u]=0;
for(int v=i; v<=j; ++v ){
sum[u] +=data[u][v];
}
if(u==0){
dp[u]=sum[u];
}else{
if(dp[u-1]>0){
dp[u]=dp[u-1]+sum[u];
}else{
dp[u]=sum[u];
}
}
if(max<dp[u]){
max=dp[u];
}
}
}
}
return max;
}

int main()
{
int n,maxvalue;
char ch;
while(cin>>n){
getchar();
input_matrix(n);
//print_matrix(n);
maxvalue=sovle(n);
cout<<maxvalue<<endl;
}
return 0;
}
[/code]
PS:写完之后,直接ac。
参考:
1.http://blog.csdn.net/lishuhuakai/article/details/8142671