LA 4327 多段图

题目链接：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 ;

 }

巴特西

LA 4327 多段图

最新文章

热门文章