Problem - 2194E - Codeforces维护起点到ij 的距离以及ij到结尾的最大权值 那么包含某个点的最大权值就出来了我们维护一下同一条对角线上所有点的最大路径权值的最大值和第二大值然后对于每个路径 一定都会经过每个对角线的一个点 然后我们枚举每个点作为变成负数的点那么这个点的最大路径就是走这条路的最大值也就是最大值-2a[i][j] 或者是不走这条路 走经过这条对角线的最大的那条 如果已经是最大的就选第二大的至于为什么选择对角线 因为不选ij 就代表i j 点所在的对角线上没有元素 那么就要在这条对角线上选择一个元素 所以维护了某个对角线上的最大路径代码如下#include bits/stdc.h using namespace std; #define int long long const int INF 1e18; void solve(){ int n,m; cinnm; vectorvectorinta(n2,vectorint(m2)),s2(n2,vectorint(m2)),s1(n2,vectorint(m2)); for(int i1;in;i){ for(int j1;jm;j){ cina[i][j]; if(i1j1)s1[i][j]a[i][j]; else if (i 1) { s1[i][j] s1[i][j-1] a[i][j]; } else if (j 1) { s1[i][j] s1[i-1][j] a[i][j]; } else { s1[i][j] max(s1[i-1][j], s1[i][j-1]) a[i][j]; } } } for (int i n; i 1; i--) { for (int j m; j 1; j--) { if (i n j m) { s2[i][j] a[i][j]; } else if (i n) { s2[i][j] s2[i][j1] a[i][j]; } else if (j m) { s2[i][j] s2[i1][j] a[i][j]; } else { s2[i][j] max(s2[i1][j], s2[i][j1]) a[i][j]; } } } vectorint m1(n m 2, -INF); vectorint m2(n m 2, -INF); for(int i1;in;i){ for(int j1;jm;j){ int kij; int tots1[i][j]s2[i][j]-a[i][j]; if(totm1[k]){ m2[k]m1[k]; m1[k]tot; }else if(totm2[k])m2[k]tot; } } int ansINF; for(int i1;in;i){ for(int j1;jm;j){ int kij; int tots1[i][j]s2[i][j]-a[i][j]; int no(totm1[k])?m2[k]:m1[k]; int yestot-2*a[i][j]; ansmin(ans,max(yes,no)); } } coutans\n; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cint; while(t--)solve(); return 0; }