【3-10最大长方体问题】。。。动态规划题越来越难了 时常是一下午一道题 还有大半是看别人代码看懂的一小部分 反正是爱好吧 。。。 其实坚持长了 慢慢就成爱好了
话说这题的基础是最大子段和问题 由最大子段和问题又可求最大子矩阵 进而求得最大长方体
这代码是别人写的 我尽量注释我的理解。。。
#include
#include
#include
using namespace std;
int MaxSum(int n,int *a);
int MaxSum2(int m,int n,int a[][50]);
int MaxSum3(int m,int n,int p,int a[][50][50]);
int main()
{
freopen("in.txt","r",stdin);
int m,n,p;
scanf("%d%d%d",&m,&n,&p);
int a[50][50][50];
memset(a,0,sizeof(a));
for(int i=1;
i<=m;
i++)
{
for(int j=1;
j<=n;
j++)
{
for(int k=1;
k<=p;
k++)
{
scanf("%d",&a[i][j][k]);
}
}
}
printf("%d\n",MaxSum3(m,n,p,a));
return 0;
}
int MaxSum(int n,int *a) //最大子段和问题的dpb代表到目前i为止的最大子段和 也就是一定要加a[i] 这个理解极为重要 接下来 如果b>0 因为一定要算a[i] 所以b+=a[i] 否则b=a[i]
{
int sum=0,b=0;
for(int i=1;
i<=n;
i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
return sum;
}
int MaxSum2(int m,int n,int a[][50])//因为要求的是二维矩阵 所以肯定要双重循环了 b[k]表示到矩阵从上至目前行的累加 因为一定要算j行 所以b[k]从j行从上至下累加
{
int sum=0;
int b[50];
memset(b,0,sizeof(b));
for(int i=1;
i<=m;
i++)
{
for(int k=1;
k<=n;
k++)
{
b[k]=0;
}
for(int j=i;
j<=m;
j++)
{
for(int k=1;
k<=n;
k++)
{
b[k]+=a[j][k];
}
int max=MaxSum(n,b);
if(max>sum)
sum=max;
}
}
return sum;
}
int MaxSum3(int m,int n,int p,int a[][50][50])//长方体的底部是二维矩阵 所以外层要双重循环 而对长方体的每个竖切面 要算面的和 类比二维矩阵的计算
{
int sum=0;
int b[50][50];
memset(b,0,sizeof(b));
for(int i=1;
i<=m;
i++)
{
memset(b,0,sizeof(b));
for(int j=i;
j<=m;
j++)
{
for(int k1=1;
k1<=n;
k1++)
for(int k2=1;
k2<=p;
k2++)
{
b[k1][k2]+=a[j][k1][k2];
}
int max=MaxSum2(n,p,b);
if(max>sum)
sum=max;
}
}
return sum;
}
