hihocoder 1580 Matrix 1634 Puzzle Game

Matrix 1634 Puzzle Game"/>

hihocoder 1580 Matrix 1634 Puzzle Game

1580 Matrix:

题意：给你一个n × m的矩阵，你需要吧其中一个数变成p，然后找一个子矩阵，子矩阵的所有数之和最大

题解：dp+rmq，枚举子矩阵的上边界和下边界，然后从左到右的dp，dp转移方程：

dp[k][0]=max(dp[k-1][0],0)+sum(a[i][k]~a[k][j])

dp[k][1]=max(max(dp[k-1][0],0)-min(a[i][k]~a[j][k])+p, dp[k-1][1])+sum(a[i][k]~a[k][j])

其中sum(a[i][k]~a[k][j])表示a[i][k]到a[k][j]的和，min(a[i][k]~a[j][k])表示a[i][k]到a[k][j]的最小值，这个用rmq得到

最后ans与dp[k][0]和dp[k][1]取最大值，不过注意不可取未修改过的原矩阵，也就是上边界为1，下边界为n，dp[m][0]为原矩阵所以数之和的情况，这是表示矩阵未被修改

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 305
using namespace std;
typedef long long ll;
const int inf=1e9+7;
int a[N][N],dp[N][2],f[N][N][10],sum[N][N],len[N];
int rmq(int k,int i,int j)
{int d=len[j-i+1];return min(f[k][i][d],f[k][j-(1<<d)+1][d]);
}
int main ()
{int n,m,p;len[1]=0;for(int i=2;i<N;i++)len[i]=(i&(i-1))==0?len[i-1]+1:len[i-1];while(~scanf("%d%d%d",&n,&m,&p)){int tot=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);f[j][i][0]=a[i][j];tot+=a[i][j];}}for(int i=1;i<=m;i++){for(int k=1;k<10;k++){for(int j=1;j+(1<<k)<=n+1;j++){f[i][j][k]=min(f[i][j][k-1],f[i][j+(1<<(k-1))][k-1]);}}for(int j=1;j<=n;j++)sum[i][j]=sum[i][j-1]+a[j][i];}int ans=p;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){for(int k=1;k<=m;k++)dp[k][0]=dp[k][1]=-inf;for(int k=1;k<=m;k++){int x=sum[k][j]-sum[k][i-1];dp[k-1][0]=max(dp[k-1][0],0);dp[k][0]=dp[k-1][0]+x;dp[k][1]=dp[k-1][0]+x-rmq(k,i,j)+p;if(k>1)dp[k][1]=max(dp[k][1],dp[k-1][1]+x);ans=max(ans,dp[k][1]);if(k==m&&i==1&&j==n&&dp[k][0]==tot);else ans=max(ans,dp[k][0]);}}}printf("%d\n",ans);}return 0;
}

这是上面那题的升级版，不过做法完全不同，我说的只是我的一个做法，虽然也不是我想出来的

题意：这里是求子矩阵和的最大值最小，并且如果修改一个数为p会使答案增大，则可以选择不修改

题解：这题的想法完全不同，我本来想着把上面那题的代码改一改就好了，可是发现完全不对，dp的意思不符合要求。这里我们可以暴力枚举所有的数，如果把它修改了会的到一个新的子矩阵最大值，把它与ans取个最小值即可；问题就在于如何得到修改任意一个数之后，如何得到最大值，这就需要预处理，n3的预处理，对于a[i][j]这个数，如果它小于p那么把它修改之后子矩阵最大值必定不会减小，所以可以不用管，修改后的最大值可能有5中情况：

在前i-1行，i+1到n行，前j-1列，j+1到m列这四个区域中的子矩阵最大值，以及原来的最大值-a[i][j]+p这5中情况，ans与这5中情况的最大值取个最小就是答案，至于如何求着四个区域的子矩阵最大值就需要上一题的做法，枚举上下边界，把得到的值更新到它可以属于的区域，枚举左右边界，更新，就得到了那四个区域的答案，我就是这里坑了，想当然了

代码：

#include<bits/stdc++.h>
#define P pair<int,int>
#define N 155
using namespace std;
typedef long long ll;
const int inf=1e9+7;
const ll M=19260817;
int a[N][N],u[N],d[N],l[N],r[N];
int sum1[N][N],sum2[N][N];
int main()
{int n,m,p,t;while(~scanf("%d%d%d",&n,&m,&p)){for(int i=0;i<N;i++)l[i]=u[i]=r[i]=d[i]=-inf;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);sum2[i][j]=sum2[i][j-1]+a[i][j];}}for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)sum1[i][j]=sum1[i][j-1]+a[j][i];for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){t=-inf;int tmp=-inf;for(int k=1;k<=m;k++){t=max(0,t)+sum1[k][max(i,j)]-sum1[k][min(i,j)-1];tmp=max(t,tmp);}for(int k=j;k<=n;k++)u[k]=max(u[k],tmp);for(int k=1;k<=i;k++)d[k]=max(d[k],tmp);}}for(int i=1;i<=m;i++){for(int j=i;j<=m;j++){t=-inf;int tmp=-inf;for(int k=1;k<=n;k++){t=max(0,t)+sum2[k][max(i,j)]-sum2[k][min(i,j)-1];tmp=max(tmp,t);}for(int k=j;k<=m;k++)l[k]=max(l[k],tmp);for(int k=1;k<=i;k++)r[k]=max(r[k],tmp);}}int ans=u[n];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]<=p)continue;int tmp=max(u[i-1],d[i+1]);tmp=max(tmp,max(l[j-1],r[j+1]));tmp=max(tmp,u[n]-a[i][j]+p);ans=min(ans,tmp);}}printf("%d\n",ans);}return 0;
}