题意：在n*m的矩阵中选择变换或者不变换一个数变成p，使得最大子矩阵和最小

1<=n,m<=150, -1000<=p<=1000;

题解：

涉及到知识点求最大矩阵和 :

memset(ma,0x88,sizeof(ma));    memset(dp,0,sizeof(dp));    ans=-inf;    for(int i=1;i<=n;i++)    {        for(int l=1;l<=m;l++)        {            sum=0;            for(int r=l;r<=m;r++)            {                sum+=a[i][r];                dp[l][r]+=sum;                ma[l][r]=max(ma[l][r],dp[l][r]);                if(dp[l][r]<0)                    dp[l][r]=0;                ans=max(ans,ma[l][r]);            }        }    }

往四个方向dp

#include
    
     using namespace std;const int inf = 2e9+1e8;const int N = 160;int a[N][N];int L[N],R[N],U[N],D[N],dp[N][N];int ma[N][N];int max4(int a,int b,int c,int d){    return max(max(a,b),max(c,d));}int n,m,p;void solve(){    int sum=0,tmp;    memset(ma,0x88,sizeof(ma));    memset(dp,0,sizeof(dp));    tmp=-inf;    for(int i=1;i<=n;i++)    {        for(int l=1;l<=m;l++)        {            sum=0;            for(int r=l;r<=m;r++)            {                sum+=a[i][r];                dp[l][r]+=sum;ma[l][r]=max(ma[l][r],dp[l][r]);                if(dp[l][r]<0)                {                    dp[l][r]=0;                }                                tmp=max(tmp,ma[l][r]);            }        }        U[i]=tmp;    }    memset(ma,0x88,sizeof(ma));    memset(dp,0,sizeof(dp));    tmp=-inf;    for(int i=n;i>=1;i--)    {        for(int l=1;l<=m;l++)        {            sum=0;            for(int r=l;r<=m;r++)            {                sum+=a[i][r];                dp[l][r]+=sum;ma[l][r]=max(ma[l][r],dp[l][r]);                if(dp[l][r]<0)                {                    dp[l][r]=0;                }                                tmp=max(tmp,ma[l][r]);            }        }        D[i]=tmp;    }    memset(ma,0x88,sizeof(ma));    memset(dp,0,sizeof(dp));    tmp=-inf;    for(int i=m;i>=1;i--)    {        for(int s=1;s<=n;s++)        {            sum=0;            for(int x=s;x<=n;x++)            {                sum+=a[x][i];                dp[s][x]+=sum;ma[s][x]=max(ma[s][x],dp[s][x]);                if(dp[s][x]<0)                {                    dp[s][x]=0;                }                                tmp=max(tmp,ma[s][x]);            }        }        R[i]=tmp;    }    memset(ma,0x88,sizeof(ma));    memset(dp,0,sizeof(dp));    tmp=-inf;    for(int i=1;i<=m;i++)    {        for(int s=1;s<=n;s++)        {            sum=0;            for(int x=s;x<=n;x++)            {                sum+=a[x][i];                dp[s][x]+=sum;ma[s][x]=max(ma[s][x],dp[s][x]);                if(dp[s][x]<0)                {                    dp[s][x]=0;                }                                tmp=max(tmp,ma[s][x]);            }        }        L[i]=tmp;    }}int main(){   // int n,m,p;    while(scanf("%d%d%d",&n,&m,&p)!=EOF)    {        memset(L,0x88,sizeof(L));        memset(R,0x88,sizeof(R));        memset(D,0x88,sizeof(D));        memset(U,0x88,sizeof(U));        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)                scanf("%d",&a[i][j]);        solve();        int ans=D[1];        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                if(a[i][j]<=p) continue;                int tmp=max4(L[j-1],R[j+1],U[i-1],D[i+1]);                tmp=max(tmp,D[1]-a[i][j]+p);                ans=min(ans,tmp);            }        }        printf("%d\n",ans);    }    return 0;}
    

体会：巧妙利用预处理的方法降低复杂度，用空间去换时间，不要被模板给限制住思维。。。。比赛中一直用模板，使得思维变得僵硬