首页 > 代码库 > URAL_1146/uva_108 最大子矩阵 DP 降维

URAL_1146/uva_108 最大子矩阵 DP 降维

2024-07-12 07:31:31   215人阅读

题意很简单，给定一个N*N的大矩阵，求其中数值和最大的子矩阵。

一开始找不到怎么DP，没有最优子结构啊，后来聪哥给了我思路，化成一维，变成最大连续和即可。为了转化成一维，必须枚举子矩阵的宽度，通过预处理的suffix可以很快计算出每一列某一段的和，然后进行一维DP即可。。总复杂度为 O(N^3);

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int mat[110][110];int suffix[110][110];int n;int main(){    while (scanf("%d",&n)!=EOF)    {        for (int i=1; i<=n; i++)        {            for (int j=1; j<=n; j++)            {                scanf("%d",&mat[i][j]);            }        }        //memset(suffix,0,sizeof suffix);        for (int i=1; i<=n; i++)        {            for (int j=1; j<=n; j++)            {                suffix[i][j]=suffix[i][j-1]+mat[i][j];            }        }        int d=0;        int ans=0;        for (int i=1; i<=n; i++)        {            for (int j=i; j<=n; j++)            {                d=0;                for (int k=1; k<=n; k++)                {                    int tmp=suffix[k][j]-suffix[k][i-1];                    if (d+tmp>tmp) d+=tmp;                    else d=tmp;                    ans=max(d,ans);                }            }        }        printf("%d\n",ans);    }    return 0;}

　　


联系
我们