#1580 : Matrix

時(shí)間限制:1000ms

單點(diǎn)時(shí)限:1000ms

內(nèi)存限制: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 4 3 3 -1 -2 -2 -2 -2 -2 -2 -2 -2 -2樣例輸出24 -1題意：給你一個(gè)n × m的矩陣，你必須把其中一個(gè)數(shù)變成p，然后找一個(gè)子矩陣，子矩陣的所有數(shù)之和最大。思路：對(duì)于一個(gè)給定的矩陣，我們要使它的和最大，那一定是把這個(gè)矩陣中最小的數(shù)改成p，所以我們需要維護(hù)一個(gè)最小值，二維的最小值很難維護(hù)，所以我們維護(hù)的是一維的。做法和最大子區(qū)間和一樣，i，j枚舉的是上下邊界，k枚舉列。dp[k][0]表示前k列沒(méi)有改數(shù)字得到的最大矩陣和。dp[k][1]表示前k列修改一個(gè)數(shù)字得到的最大矩陣和。mp[k]表示的是在【i，j】區(qū)間內(nèi)第k列的最小值。dp[k][0]=max(dp[k-1][0],0)+sum[k];dp[k][1]=max(dp[k-1][1]+sum[k],max(dp[k-1][0],0)+sum[k]-mp[k]+p);#include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> using namespace std; int n,m,p,ans,a[500][500],sum[500],mp[500],dp[500][2]; int main() { while(~scanf("%d%d%d",&n,&m,&p)){int ans=-1000000000,ms=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),ms+=a[i][j];for(int i=1;i<=n;i++){dp[0][0]=0;memset(sum,0,sizeof(sum));for(int j=i;j<=n;j++){for(int k=1;k<=m;k++){sum[k]+=a[j][k];if(i==j) mp[k]=a[j][k]; else mp[k]=min(mp[k],a[j][k]);dp[k][0]=max(dp[k-1][0],0)+sum[k];if(i==1&&j==n&&k==m&&dp[k][0]==ms) ; else ans=max(ans,dp[k][0]);//如果不是整個(gè)矩陣的話，可以修改矩陣外的任意一點(diǎn)使其達(dá)到題目要求,注意一定要是dp[k][0]==ms,保證是整個(gè)矩陣。 if(k>1) dp[k][1]=max(dp[k-1][1]+sum[k],max(dp[k-1][0],0)+sum[k]-mp[k]+p);else dp[k][1]=sum[k]-mp[k]+p;ans=max(ans,dp[k][1]);}} } printf("%d\n",ans);} }

轉(zhuǎn)載于:https://www.cnblogs.com/The-Pines-of-Star/p/9878834.html

總結(jié)

以上是生活随笔為你收集整理的hihocoder 1580 Matrix（北京icpc2017网络赛）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。