解题思路:
首先,要把行列分开处理,假设选择 i 次行 , k - i 次列 ,如果先选行 ,那么当选择列时每选择一次列就减去 i*p ,选择 k - i 次列就减去 i * (k - i ) * p ,所以我们可以先单独处理行,然后单独处理列,最后只要减去 i * (k - i ) * p 即可。
代码:
#include<iostream> #include<fstream> #include<iomanip> #include<ctime> #include<fstream> #include<sstream> #include<stack> #include<cstring> #include<cmath> #include<map> #include<queue> #include<vector> #include<cstdio> #include<algorithm> #define INT __int64 using namespace std ; const double esp = 0.00000001 ; const INT INF = 9999999 ; const INT mod = 1e9 + 7 ; const INT MY = 200 + 10 ; const INT MX = 1000 + 10 ; INT n ,m , p ,k ; priority_queue<INT>row ,col ; INT a[MX] ,b[MX] ,R[MX*MX] ,L[MX*MX] ; void input() { INT x ; memset(a ,0 ,sizeof(a)) ; memset(b ,0 ,sizeof(b)) ; for(INT i = 0 ;i < n ; ++i) for(INT j = 0 ;j < m ; ++j) { scanf("%I64d" ,&x) ; a[i] += x ; b[j] += x ; } while(!row.empty()) row.pop() ; while(!col.empty()) col.pop() ; for(INT i = 0 ;i < n ; ++i) row.push(a[i]) ; for(INT i = 0 ;i < m ; ++i) col.push(b[i]) ; } void solve() { INT temp ; memset(R ,0 ,sizeof(R)) ; memset(L ,0 ,sizeof(L)) ; for(INT i = 1 ;i <= k ; ++i) { temp = row.top() ; row.pop() ; R[i] += temp + R[i-1] ; row.push(temp - p*m) ; } for(INT i = 1 ;i <= k ; ++i) { temp = col.top() ; col.pop() ; L[i] += temp + L[i-1] ; col.push(temp - p*n) ; } INT ans = L[k] ; for(INT i = 1 ;i <= k ; ++i) ans = max(ans ,R[i] + L[k-i] - i*(k-i)*p) ; cout<<ans<<endl ; } int main() { while(~scanf("%I64d%I64d%I64d%I64d" ,&n ,&m ,&k ,&p)) { input() ; solve() ; } return 0 ; }