题目描述：
有一个 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[1010][1010],sumr[1010],suml[1010],dp1[1000010],dp2[1000010]; int n,m,k,p; int main() { scanf("%d%d%d%d",&n,&m,&k,&p); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { scanf("%lld",&a[i][j]); } } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { sumr[i]+=a[i][j]; } } for(int i=1; i<=m; i++) { for(int j=1; j<=n; j++) { suml[i]+=a[j][i]; } } priority_queue<long long> q,q2; for(int i=1; i<=n; i++) { q.push(sumr[i]); } for(int i=1; i<=k; i++) { long long tmp=q.top(); q.pop(); dp1[i]=dp1[i-1]+tmp; tmp-=1ll*m*p; q.push(tmp); } for(int i=1; i<=m; i++) { q2.push(suml[i]); } for(int i=1; i<=k; i++) { long long tmp=q2.top(); q2.pop(); dp2[i]=dp2[i-1]+tmp; tmp-=1ll*n*p; q2.push(tmp); } for(int i=1; i<=k; i++) { dp2[i]-=1ll*i*(k-i)*p; } long long ans=-1e18; for(int i=0; i<=k; i++) { ans=max(ans,dp1[i]+dp2[k-i]); } printf("%lld ",ans); }