题目描述：
有一个 n×m的矩阵，现在准备对矩阵进行k次操作，每次操作可以二选一
1:
选择一行，给这一行的每一个数减去p，这种操作会得到的快乐值等于操作之前这一行的和
2:
选择一列，给这一列的每一个数减去p，这种操作会得到的快乐值等于操作之前这一列的和
那么问题来了，k次操作最大可能得到的和是多少。
输入格式：
第一行输入4个整数n,m,k,p
接下来n行，每行输入m个整数a[i][j]
输出格式：
输出最大可能的和
样例输入1：
2 2 2 2
1 3
2 4
样例输出1：
11
样例输入2：
5 5 20 100
464 757 53 708 262
753 769 189 38 796
394 60 381 384 935
882 877 501 615 464
433 798 504 301 301
样例输出2：
38013
样例输入3：
2 1 3 2
3
3
样例输出3：
8
约定：
1≤n,m≤1000,1≤k≤106,1≤p,a[i][j]≤1000
题解：
首先观察第三个样例，显然将行和列和压入优先队列搞k次是不现实的，
因为最大值应该是取第一列、第一行、第二行，答案为8，
如果按上述方法搞会取出两次第一列，一次第一或第二行，答案为7
为什么会造成这种结果？
因为每次取行的时候我们并没有想到对列的值也会产生变化，并且这种取法有后效性。
所以索性先取行后取列
枚举取一次、两次……k次行，相对应会取k-1、k-2……1次列
记dp_row[i]表示取i次行获得的最大值，这个显然可以用优先队列瞎搞
同样dp_colomn[i]表示取y次行获得的最大值，也可以用优先队列瞎搞
先取行再取列会使列的值损失，损失多少呢？
假设取i次列，k-i次行
每行损失i*p
共k-i行
共损失i*(k-i)*p
于是状态转移方程就推出来了
ans=max{ans,dp_row[i]+dp_colomn[k-i]-i*(k-i)*p}
注意这个数可能会非常小，所以ans一定要设成-1e18，不能用-0x3f3f3f3f
代码如下：
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; long long a[][],sumr[],suml[],dp1[],dp2[];
int n,m,k,p; int main()
{
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
scanf("%lld",&a[i][j]);
}
}
for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
sumr[i]+=a[i][j];
}
}
for(int i=; i<=m; i++)
{
for(int j=; j<=n; j++)
{
suml[i]+=a[j][i];
}
}
priority_queue<long long> q,q2;
for(int i=; i<=n; i++)
{
q.push(sumr[i]);
}
for(int i=; i<=k; i++)
{
long long tmp=q.top();
q.pop();
dp1[i]=dp1[i-]+tmp;
tmp-=1ll*m*p;
q.push(tmp);
}
for(int i=; i<=m; i++)
{
q2.push(suml[i]);
}
for(int i=; i<=k; i++)
{
long long tmp=q2.top();
q2.pop();
dp2[i]=dp2[i-]+tmp;
tmp-=1ll*n*p;
q2.push(tmp);
}
for(int i=; i<=k; i++)
{
dp2[i]-=1ll*i*(k-i)*p;
}
long long ans=-1e18;
for(int i=; i<=k; i++)
{
ans=max(ans,dp1[i]+dp2[k-i]);
}
printf("%lld\n",ans);
}