传送门 点击打开链接
在特判的时候遵照dp原则莫名写崩了，期望大佬指出，特判改成暴力就ac了， 期望大佬指出错误 多谢
降维，dp好题
#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<cctype>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int maxn = 310 ;
const int inf = 0x3f3f3f3f;
int n , m , p ;
int dp[maxn][2] , ma[maxn][maxn] , sum[maxn] , minVal[maxn];
int max_matrix(){int ans = - inf ;memset(dp , 0 , sizeof(dp)) ;dp[0][0] = sum[0] ;dp[0][1] = sum[0] - minVal[0] + p ;ans = max(dp[0][0] , dp[0][1]) ;for(int i = 1 ; i < m ; i ++ ){dp[i][0] = max(dp[i-1][0] , 0) + sum[i] ;dp[i][1] = max(dp[i-1][1] + sum[i] , max(dp[i-1][0] ,0 ) + sum[i] + p - minVal[i]) ;ans = max(ans , max(dp[i][0] , dp[i][1])) ;}return ans ;
}
int te_pan(){int ans = -inf ;int pre_sum = 0 , min_total = inf ;memset(dp , 0 ,sizeof(dp)) ;dp[0][0] = sum[0] ;dp[0][1] = sum[0] - minVal[0] + p ;ans = max(dp[0][0] , dp[0][1]) ;for(int i = 1 ; i < m ; i ++ ){if(i == m - 1){for(int j = 0 ; j < m ; j ++ ) pre_sum += sum[j] , min_total = min(min_total , minVal[j]);ans = max(ans , pre_sum - min_total + p) ;}else{dp[i][0] = max(dp[i-1][0] , 0) + sum[i] ;dp[i][1] = max(dp[i-1][1] + sum[i] , max(dp[i-1][0] + sum[i] - minVal[i] + p , sum[i] + p - minVal[i])) ;ans = max(ans , max(dp[i][0] , dp[i][1])) ;}}return ans ;
}///莫名wa
int baoli(){int ans = -inf ;for(int i = 0 ; i < m ; i ++ ){int pre_sum = 0 ;int min_total = inf ;for(int j = i ; j < m ; j ++ ){pre_sum += sum[j] ;min_total = min(min_total , minVal[j]) ;if(i == 0 && j == m - 1) ans = max(ans , pre_sum - min_total + p) ;else ans = max(ans , max(pre_sum , pre_sum - min_total + p)) ;}}return ans ;
}int work(){int ans = -inf ;for(int i = 0 ; i < n ; i ++ ){memset(sum , 0 , sizeof(sum)) ;memset(minVal , 0x7f, sizeof(minVal));for(int j = i ; j < n ; j ++ ){for(int k = 0 ; k < m ; k ++ ){minVal[k] = min(minVal[k] , ma[j][k]);sum[k] += ma[j][k];}if(i == 0 && j == n - 1 ) ans = max(ans , baoli()) ;else ans = max(ans , max_matrix()) ;}}return ans ;
}int main(){while( ~ scanf("%d %d %d" , &n , &m , &p)){memset(ma , 0 , sizeof(ma)) ;for(int i = 0 ; i < n ; i ++ )for(int j = 0 ; j < m ; j ++ )scanf("%d" , & ma[i][j]) ;printf("%d\n" , work()) ;}return 0 ;
}