题目链接：https://vjudge.net/contest/164840#problem/B
题意：
从南往北走，横向的时间不能超过 c；
横向路上有权值，求权值最大；
分析：
n<=100,m<=10000
数据范围很大了，基本上要n*m；
分析每个交叉路口，每个交叉路口，可以从下一行的左边，或者下一行的右边过来；
那么这个交叉路口就是max(L[j],R[j])；
怎么得到，某一个交叉路口从左边来，可以有哪些点呢？ 不可能循环跑一遍（m的范围）；
就用了一个Ｑ双端队列来维护；
怎么得到，从哪个点上来最优呢？ 在这个队列中的点也不能循环跑一遍；
还是利用这个队列；维护他这个队列是单调队列就好了，
#include <bits/stdc++.h> using namespace std; #define LL long long const int maxn = ;
const int maxm = ;
LL f[maxn][maxm],t[maxn][maxm],L[maxm],R[maxm],n,m,c,d[maxn][maxm]; deque<int> Q;
int Lfunc(int j,int i) {
return d[i-][j] - f[i][j];
} int Rfunc(int j,int i) {
return d[i-][j] + f[i][j];
} int main() {
while(scanf("%lld %lld %lld",&n,&m,&c)==&&n) {
for(int i=; i<=n+; i++)
for(int j=; j<=m; j++) {
if(!j) f[i][j] = ;
else {
scanf("%lld",&f[i][j]);
f[i][j]+=f[i][j-];
}
} for(int i=; i<=n+; i++)
for(int j=; j<=m; j++) {
if(!j) t[i][j] = ;
else {
scanf("%lld",&t[i][j]);
t[i][j]+=t[i][j-];
}
} for(int i=; i<=m; i++)
d[][i] = ; for(int i=; i<=n+; i++) {
L[] = d[i-][];
Q.clear();
Q.push_back();
for(int j=; j<=m; j++) {
while(!Q.empty()&&t[i][j]-t[i][Q.front()]>c) {
Q.pop_front();
}
L[j] = d[i-][j]; //从左到达 j 的最优值
if(!Q.empty()) L[j] =max(L[j],Lfunc(Q.front(),i)+f[i][j]);
while(!Q.empty()&&Lfunc(Q.back(),i)<=Lfunc(j,i)) Q.pop_back();
Q.push_back(j);
} R[] = d[i-][m];
Q.clear();
Q.push_back(m);
for(int j=m-; j>=; j--) {
while(!Q.empty()&&t[i][Q.front()]-t[i][j]>c) Q.pop_front();
R[j] = d[i-][j];
if(!Q.empty()) R[j] = Rfunc(Q.front(),i)-f[i][j];
while(!Q.empty()&&Rfunc(Q.back(),i)<=Rfunc(j,i)) Q.pop_back();
Q.push_back(j);
}
for(int j=; j<=m; j++)
d[i][j] = max(L[j],R[j]);
} LL res;
for(int i=; i<=m; i++) {
if(!i) res=d[n+][i];
else res = max(d[n+][i],res);
}
printf("%lld\n",res);
}
return ;
}