选数字

题目描述&＃xff1a;
LYK 找到了一个 n*m 的矩阵&＃xff0c;这个矩阵上都填有一些数字&＃xff0c;对于第 i 行第 j 列的位置上的数为 ai,j。
由于它 AK 了 noip2016 的初赛&＃xff0c;最近显得非常无聊&＃xff0c;便想到了一个方法自娱自乐一番。
它想到的游戏是这样的&＃xff1a;每次选择一行或者一列&＃xff0c;它得到的快乐值将会是这一行或者一列的数字之和。之后它将该行或者该列上的数字都减去 p&＃xff08;之后可能变成负数&＃xff09;。如此&＃xff0c;重复 k次&＃xff0c;它得到的快乐值之和将会是它 NOIP2016 复赛比赛时的 RP 值。
LYK 当然想让它的 RP 值尽可能高&＃xff0c;于是它来求助于你。
输入格式&＃xff1a;
第一行 4 个数 n,m,k,p.
接下来 n 行 m 列&＃xff0c;表示 ai,j。
输出格式&＃xff1a;
输出一行表示最大 RP 值。
输入样例&＃xff1a;
2 2 5 2
1 3
2 4
输出样例&＃xff1a;
11
数据范围&＃xff1a;
总共 10 组数据。
对于第 1,2 组数据 n,m,k<&＃61;5。
对于第 3 组数据 k&＃61;1。
对于第 4 组数据 p&＃61;0。
对于第 5,6 组数据 n&＃61;1&＃xff0c; m,k<&＃61;1000。
对于第 7,8 组数据 n&＃61;1&＃xff0c; m<&＃61;1000&＃xff0c; k<&＃61;1000000。
对于所有数据 1<&＃61;n,m<&＃61;1000&＃xff0c; k<&＃61;1000000&＃xff0c; 1<&＃61;ai,j<&＃61;1000&＃xff0c; 0<&＃61;p<&＃61;100。
样例解释&＃xff1a;
第一次选择第二列&＃xff0c;第二次选择第二行&＃xff0c;第三次选择第一行&＃xff0c;第四次选择第二行&＃xff0c;第五次选择第一行&＃xff0c;快乐值为 7&＃43;4&＃43;2&＃43;0&＃43;-2&＃61;11。
思路&＃xff1a;
观察可以发现如果确定选几次行几次列
那么选的顺序是无所谓的
对于选行 那么肯定是选最优的 对于行也是
所以
先处理出选0~k次行和列的最优值
然后枚举选i次行则选k-i次列
行的最优值加上列的最优值减去选行和列交叉的地方多选的即可
ans&＃61;max(ans,s[i]&＃43;r[i]-(i)*(k-i)*p)

#include
#include
#include
#define lon long long
using namespace std;
const int maxn&＃61;1010;
const lon inf&＃61;-1000000000000000;
lon n,m,k,p,h[maxn*maxn],l[maxn*maxn],a[maxn][maxn];
priority_queueq;
lon init()
{lon x&＃61;0,f&＃61;1;char c&＃61;getchar();while(c<&＃39;0&＃39;||c>&＃39;9&＃39;){if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;c&＃61;getchar();}while(c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;c-&＃39;0&＃39;;c&＃61;getchar();}return x*f;
}
int main()
{freopen("select.in","r",stdin);freopen("select.out","w",stdout);n&＃61;init(),m&＃61;init(),k&＃61;init(),p&＃61;init();for(lon i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(lon j&＃61;1;j<&＃61;m;j&＃43;&＃43;)a[i][j]&＃61;init();for(lon i&＃61;1;i<&＃61;n;i&＃43;&＃43;){lon sum&＃61;0;for(lon j&＃61;1;j<&＃61;m;j&＃43;&＃43;)sum&＃43;&＃61;a[i][j];q.push(sum);}for(lon i&＃61;1;i<&＃61;k;i&＃43;&＃43;){lon sum&＃61;q.top();q.pop();h[i]&＃61;h[i-1]&＃43;sum;q.push(sum-p*m);}while(!q.empty()) q.pop();for(lon j&＃61;1;j<&＃61;m;j&＃43;&＃43;){lon sum&＃61;0;for(lon i&＃61;1;i<&＃61;n;i&＃43;&＃43;)sum&＃43;&＃61;a[i][j];q.push(sum);}for(lon i&＃61;1;i<&＃61;k;i&＃43;&＃43;){lon sum&＃61;q.top();q.pop();l[i]&＃61;l[i-1]&＃43;sum;q.push(sum-p*n);}lon ans&＃61;inf;for(lon i&＃61;0;i<&＃61;k;i&＃43;&＃43;)ans&＃61;max(ans,h[i]&＃43;l[k-i]-i*(k-i)*p);cout<return 0;
}