Poj 1050 动态规划

题目大意：给一个方矩阵，求解元素和最大的子矩阵。最终要求输出最大和结果。

题目分析：一位数组的最大和通过动态规划是很好解决的，利用如下递推公式即可：

思路清晰了，但是代码还是很多次没过，原因就是超时。
之前的思路是这样的：循环i为一行、两行、三行、四行的情况。内层循环j为结束行。定义一个数组B存储结果，对于每一行的k列，k再进行一个循环。然后第k个元素需要从j-i行加到j行，这又需要一层循环。一共是四层循环，这就肯定超时了。

后来改进了一下，变成了三层循环。重新定义了i和j，定义i为起始行，j为结束行。这样i从1到N，j从i到N，就可以遍历所有的情况。在ij内层定义一个k循环，计算 B[k]+=A[j][k] 。这样随着j增加，B[k]会变成多行之和，然后改变i的时候初始化一下B即可。这样就变成三层循环了，顺利通过。可见这个程序的设计还是需要多加考虑的。

#include <iostream>
#include <cstring>
using namespace std;
int N;
int A[510][510];
int B[510];
int dp[510];
int ans = -9999;
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> A[i][j];
}
}
for (int i = 0; i < N; i++)
{
memset(B,0, sizeof(B));
for (int j = i; j < N; j++)
{
for (int k = 0; k < N; k++)
{
B[k] += A[j][k];
if (!k)
dp[0] = B[0];
else
dp[k] = dp[k - 1]>0 ? dp[k - 1] + B[k] : B[k];
ans = dp[k] > ans ? dp[k] : ans;
}
}
}
cout << ans << endl;
//system("pause");
return 0;
}

最后

以上就是魔幻哈密瓜为你收集整理的Poj 1050 动态规划的全部内容，希望文章能够帮你解决Poj 1050 动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。