2017 베이징 인터넷 경기 hihocoder 1580 Matrix(dp 좋은 사고문제)

시간 제한: 1000ms 단일 시한: 1000ms 메모리 제한: 256MB 설명 Once upon a time, there was a little dog YK.One day, he went to an antique shop and was impressed by a beautiful picture. YK loved it very much.
However, YK did not have money to buy it. He begged the shopkeeper whether he could have it without spending money.
Fortunately, the shopkeeper enjoyed puzzle game. So he drew a n × m matrix on the paper with integer value ai,j in each cell. He wanted to find 4 numbers x, y, x2, and y2(x ≤ x2, y ≤ y2), so that the sum of values in the sub-matrix from (x, y) to (x2, y2) would be the largest.
To make it more interesting, the shopkeeper ordered YK to change exactly one cell’s value into P, then to solve the puzzle game. (That means, YK must change one cell’s value into P.)
If YK could come up with the correct answer, the shopkeeper would give the picture to YK as a prize.
YK needed your help to find the maximum sum among all possible choices.
There are multiple test cases 를 입력합니다.
The first line of each case contains three integers n, m and P. (1 ≤ n, m ≤ 300, -1000 ≤ P ≤ 1000).
Then next n lines, each line contains m integers, which means ai,j (-1000 ≤ ai,j ≤ 1000).
출력 For each test, you should output the maximum sum.
샘플 입력 3 3 4 - 100 4 4 4 - 10 4 4 4 3 - 1 - 2 - 2 - 2 - 2 - 2 - 2 - 2 샘플 출력 24 - 1
대체적인 제목: 행렬을 드리겠습니다. 그 중의 어떤 값을 p로 바꾸어 최대 하위 행렬과
사고방식:막일발dalao의 문제풀이http://blog.csdn.net/luricheng/article/details/78074046나의 이해: 일반적인 최대 서브 행렬의 합에 대해 우리는 보통 상하계 O(n^2)를 매거한 다음에 O(n)의 시간 안에 최대 연속 서브 단락과 합을 구한다.그리고 이 문제에 대해 우리는 어떤 값이 p로 변하도록 수정해야 한다. 그러면 최대 연속 자단을 구하는 과정에서 우리는 2차원 dp를 추가할 수 있다. dp[i][0]는 이때 i열로 끝날 때 값이 바뀌지 않았을 때의 최대 연속 자단과 dp[i][1]는 이때 i열로 끝날 때 값 p의 최대 연속 자단과 값이 바뀌었다는 것을 나타낸다.가령sum[i]가 이때 상하행 후 i열의 모든 값을 고정시키고minval[i]가 상하행 후 i열에서 가장 작은 요소의 값을 고정시킨다면 전이 방정식은 dp[i][0]=max(do[i-1][0],0)+sum[i]이다.dp[i][1]=max(dp[i-1][1]+sum[i],max(do[i-1][0],0)+sum[i]-minval[i]+p); 마지막으로 우리는 특수한 상황을 고려해야 한다. 즉, 우리가 선택한 범위가 전체 직사각형일 때, 우리는 그 중 가장 작은 값을 찾아 p로 바꾸어야 한다
코드는 다음과 같다.

#include 
using namespace std;  
const int N=305;
const int inf=-1e9-7;
const int INF=1e9+7;
int dp[N][2];
int mat[N][N];
int sum[N];
int minval[N];
int n,m,p;
int solve1()
{
    int ans=inf;
    dp[0][0]=sum[0];
    dp[0][1]=sum[0]-minval[0]+p;
    ans=max(dp[0][0],dp[0][1]);
    for(int i=1;i0]=max(dp[i-1][0],0)+sum[i];
        dp[i][1]=max(dp[i-1][1]+sum[i],max(dp[i-1][0],0)+sum[i]-minval[i]+p);
        ans=max(ans,max(dp[i][0],dp[i][1]));
    }
    return ans;
}
int solve2()//   ，        0 n-1，         
{
    int ans=inf;
    for(int i=0;iint summ=0;
        int minn=INF;
        for(int j=i;jmin(minn,minval[j]);
            if(i==0&&j==m-1)
                ans=max(ans,summ-minn+p);
            else
                ans=max(ans,max(summ,summ-minn+p)); 
        }
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)    
    {
        for(int i=0;ifor(int j=0;j"%d",&mat[i][j]);
        int ans=inf;

        for(int i=0;i//      
        {
            for(int f=0;f<=m;f++)//   
            {
                sum[f]=0;
                minval[f]=INF;
            }

            for(int j=i;j//     
            {
                for(int k=0;kmin(minval[k],mat[j][k]);
                }
                if(i==0&&j==n-1)
                    ans=max(ans,solve2());
                else 
                    ans=max(ans,solve1());
            }
        }
        printf("%d
",ans);
    }
    return 0; 
}