LA 4327 Parade（单调队列优化dp）

Dear 丶 2021-11-16 23:36 290阅读 0赞

## 题意：F城由n+1个横向路和m+1个竖向路组成。你的任务是从最南边的路走到最北边的路，使得走过的路上的高兴值和最大（高兴值可能为负值）。同一段路不能经过两次，且不能从北往南走，在每条横向路所花时间不超过k。 ##

## 分析：从南往北走和从北往南走是等价的，令d\[ i \]\[ j \]为走到( i , j )最大的高兴值，则dp\[ i \]\[ j \]=max(dp\[ i-1 \]\[ p \]+s\[ j \]-s\[ p \])，s数组为前缀和，p 到 j 所花时间不超过 k，设g\[ p \]=dp\[ i-1 \]\[ p \]-s\[ p \]，我们用一个单调递减的队列维护f\[ p \]最大值，每次更新当前点j，就把队列里g\[ p \]值小于等于g\[ j \]的值删除，确保队头（左端l）为最大值，然后把该点的值插入队列（要分从左到右和从右到左两个方向考虑d\[ i \]\[ j \]的最大值）。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4+5;
    const int M = 1e2+5;
    int n,m,k,s1[M][N],s2[M][N],d[M][N],q[N];
    void init()
    {
    	for(int i=1;i<=n+1;i++)
    	{
    		s1[i][0]=0;
    		for(int j=1;j<=m;j++)
    		{
    			scanf("%d",&s1[i][j]);
    			s1[i][j]+=s1[i][j-1];
    		}
    	}
    	for(int i=1;i<=n+1;i++)
    	{
    		s2[i][0]=0;
    		for(int j=1;j<=m;j++)
    		{
    			scanf("%d",&s2[i][j]);
    			s2[i][j]+=s2[i][j-1];
    		}
    	}
    }
    int main()
    {
    	while(~scanf("%d%d%d",&n,&m,&k)&&n&&m)
    	{
    		init();
    		int l,r;
    		for(int i=1;i<=n+1;i++)
    		{
    			l=r=0;
    			q[0]=0;
    			for(int j=0;j<=m;j++)
    			{
    				while(l<=r&&s2[i][j]-s2[i][q[l]]>k)
    				l++;
    				d[i][j]=d[i-1][j];
    				if(l<=r)
    				d[i][j]=max(d[i][j],d[i-1][q[l]]+s1[i][j]-s1[i][q[l]]);
    				while(l<=r&&d[i-1][j]>=d[i-1][q[r]]+s1[i][j]-s1[i][q[r]])
    				r--;
    				q[++r]=j;
    			}
    			r=l=0;
    			q[0]=m;
    			for(int j=m;j>=0;j--)
    			{
    				while(l<=r&&s2[i][q[l]]-s2[i][j]>k)
    				l++;
    				if(l<=r)
    				d[i][j]=max(d[i][j],d[i-1][q[l]]+s1[i][q[l]]-s1[i][j]);
    				while(l<=r&&d[i-1][j]>=d[i-1][q[r]]+s1[i][q[r]]-s1[i][j])
    				r--;
    				q[++r]=j;
    			}
    		}
    		int ans=0;
    		for(int i=0;i<=m;i++)
                ans=max(ans,d[n+1][i]);
    		printf("%d\n",ans);
    	}
    	return 0;
    }