poj1050 动态规划

题意：给定N*N的矩阵，求最大子矩阵和
算法：动态规划。枚举子矩阵a[i,j]，表示从第i行到第j行组成的矩阵，将其每列相加，即可转换为求一维数组的最大连续子段和问题。
设dp[k]表示以元素k结束的最大子段和，那么，dp[k]=max{dp[k-1]+a[k],a[k]}

#include <iostream>
#include <string.h>
using namespace std;
const int SIZE=110;
int INF = -127 * SIZE * SIZE;
int a[SIZE][SIZE];
int main()
{
int n;
cin
>> n;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
cin >> a[i][j];
}
}
int sum[SIZE][SIZE];
memset(sum,0,sizeof(sum));
int ans = INF ;
for (int i=1; i<=n; i++)
{
for (int j=i; j<=n; j++)
{
int dp[SIZE] ;
for (int k=1; k<=n; k++)
{
sum[i][k] += a[j][k];
// sum[i][k] = sum[i:j][k]
(dp[k-1] > 0)?
dp[k] = dp[k-1] + sum[i][k] : dp[k] = sum[i][k];
if (dp[k] > ans)
{
ans = dp[k];
}
}
}
}
cout << ans << endl;
}

最后

以上就是务实大山为你收集整理的poj1050 动态规划的全部内容，希望文章能够帮你解决poj1050 动态规划所遇到的程序开发问题。

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