解题思路:①如果按照对每行每列的数字进行逐一分析,很容易就超限,500可不是个小数哦~~~
②那就想怎么能通过加减运算去节省时间,不难想到相邻的行之间相加就可以得到一个子阵,所以,对输入的数据加上前面所有行的数据重新储存到数组中,这里方便区分用两个数组表示a表示储存输入数据的数组,b表示变化后的数组。b0=a0,b1=a0+a1,b2=a0+a1+a2,b3=a0+a1+a2+a3......不难看出b1-b0=a1,b2-b0=a1+a2.....这样就可以得到行上的子阵,再用一个循环去控制列的大小就可以找到每个子阵.
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
int a[550][550],dp[550][550];
int main()
{
int n,m,num=-1e5;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
a[i][j]+=a[i-1][j];
dp[i][j]=a[i][j]; //将前面几行的数都储存在数组当中
}//dp数组用于动规
}
for(int i=1;i<=n;i++)
{
for(int k=0;k<i;k++)
{
dp[550][550]={0};
for(int s=1;s<=m;s++)
{
dp[k][s]=max((a[i][s]-a[k][s]),(a[i][s]-a[k][s]+dp[k][s-1]));
num=max(dp[k][s],num);
}
}
}
cout<<num;
return 0;
}
0.0分
7 人评分
小九九 (C语言代码)浏览:817 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:623 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1307 |
C语言程序设计教程(第三版)课后习题5.7 (Java代码)浏览:887 |
本人酷爱递归实现很多问题,这里也是浏览:550 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:534 |
母牛的故事 (C语言代码)浏览:940 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:509 |
C二级辅导-计负均正 (C语言代码)浏览:480 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:570 |