本文共 864 字，大约阅读时间需要 2 分钟。

【题解】

题意：给定一个n*m的矩阵，0表示可更改为任意值，要求最后的矩形满足对于每一行从左到右，每一列从上到下的元素都是严格上升的，最后输出最大矩阵和。

思路：由题面可知0不会出现在边界的行列，那么显然我们可以知道最大临界值，所以只要每次根据最大临界值(横、竖)选择可选最大值，非0情况判断是否符合要求即可构造出最优结果。有点类似动态规划的思想，找到临界状态，就可以根据要求写出转移方程进行转移。

【代码】

#include 
   
    using namespace std;int a[505][505],n,m;int main(){    while(~scanf("%d%d",&n,&m)){        int f=1,sum=0;        for(int i=1;i<=n;i++)            for(int j=1;j<=m;j++)                scanf("%d",&a[i][j]),sum+=a[i][j];        for(int i=n;i>=1&&f;i--)            for(int j=m;j>=1;j--)                if(a[i][j]==0){                    a[i][j]=min(a[i+1][j],a[i][j+1])-1,sum+=a[i][j];                }                else{                    if((i
    
     =a[i+1][j])||(j
     
      =a[i][j+1])){                        f=0; break;                    }                }        if(f) printf("%d\n",sum);        else puts("-1");    }    return 0;}
     
    
   

转载地址：http://jhfen.baihongyu.com/