题目传送门
题意分析
考虑从左上角 \((i_1,j_1)\) 走到右下角 \((i_2,j_2)\)，只拐一次弯。
有两种走法：
-
先向右，再向下，距离为：
\[a_{i_1}(j_2-j_1)+b_{j_2}(i_2-i_1) \] -
先向下，再向右，距离为：
\[a_{i_2}(j_2-j_1)+b_{j_1}(i_2-i_1) \]
第 \(1\) 种优于第二种当且仅当：
\[\begin{aligned}
a_{i_1}(j_2-j_1)+b_{j_2}(i_2-i_1)&<a_{i_2}(j_2-j_1)+b_{j_1}(i_2-i_1)\\
(a_{i_1}-a_{i_2})(j_2-j_1)&<(b_{j_1}-b_{j_2})(i_2-i_1)\\
\dfrac{a_{i_1}-a_{i_2}}{i_2-i_1}&<\dfrac{b_{j_1}-b_{j_2}}{j_2-j_1}\\
\dfrac{a_{i_1}-a_{i_2}}{i_1-i_2}&>\dfrac{b_{j_1}-b_{j_2}}{j_1-j_2}\\
\end{aligned}
\]
因此，对于最终确定的最优路径，\((i_1,j_1)\sim(i_2,j_2)\) 的一个拐点，是拐向一条斜率小的路。
因此可以考虑删掉一些不可能成为拐点的部分，每次找最大差分即可。
找到了之后就可以删除这一行/列并更新差分。
可以使用堆或平衡树维护上述过程，链表维护删除修改即可。
例如对于数据：
6 8
3 5 1 9 4 8
3 6 7 1 8 2 5 6
看一下具体过程。（原图来自于官方题解）
AC 代码
时间复杂度：\(\mathcal O((n+m)\log(n+m))\)。
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,M=1e5;
int n,m;
int a[N+1],b[N+1],lst[2];
int del[2][N+1],L[2][N+1],R[2][N+1];
struct node{ll value;int size;int l,r,op;
};
bool operator <(node a,node b){return (ll)a.value*b.size<(ll)b.value*a.size;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}priority_queue<node>q;for(int i=2;i<=n;i++){q.push({a[i]-a[i-1],1,i-1,i,0});L[0][i]=i-1;R[0][i]=i+1;}R[0][n]=0;for(int i=2;i<=m;i++){q.push({b[i]-b[i-1],1,i-1,i,1});L[1][i]=i-1;R[1][i]=i+1;}R[1][m]=0;lst[0]=a[n],lst[1]=b[m];ll ans=0;while(q.size()){node x=q.top();q.pop();int &op=x.op,&size=x.size,&l=x.l,&r=x.r;if(del[op][l]||del[op][r]){continue;}if(!R[op][r]){R[op][L[op][r]]=0;if(!op){lst[0]=a[L[0][r]];}else{lst[1]=b[L[1][r]];}del[op][r]=true;ans+=1ll*lst[op^1]*size;}else{L[op][R[op][r]]=L[op][r];R[op][L[op][r]]=R[op][r];del[op][r]=true;int pl=L[op][r],pr=R[op][r];if(!op){q.push({a[pr]-a[pl],pr-pl,pl,pr,0});}else{q.push({b[pr]-b[pl],pr-pl,pl,pr,1});}}}cout<<ans<<'\n';cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}
/*
6 8
3 5 1 9 4 8
3 6 7 1 8 2 5 6
*/