hdu4374单一队列+dp

hdu4374单调队列+dp

http://acm.hdu.edu.cn/showproblem.php?pid=4374

Problem Description

Now there is a game called the new man down 100th floor. The rules of this game is:
　　1.  At first you are at the 1st floor. And the floor moves up. Of course you can choose which part you will stay in the first time.
　　2.  Every floor is divided into M parts. You can only walk in a direction (left or right). And you can jump to the next floor in any part, however if you are now in part “y”, you can only jump to part “y” in the next floor! (1<=y<=M)
　　3.  There are jags on the ceils, so you can only move at most T parts each floor.
　　4.  Each part has a score. And the score is the sum of the parts’ score sum you passed by.
Now we want to know after you get the 100th floor, what’s the highest score you can get.

Input

The first line of each case has four integer N, M, X, T(1<=N<=100, 1<=M<=10000, 1<=X， T<=M). N indicates the number of layers; M indicates the number of parts. At first you are in the X-th part. You can move at most T parts in every floor in only one direction.
Followed N lines, each line has M integers indicating the score. (-500<=score<=500)

Output

Output the highest score you can get.

Sample Input

Sample Output

/**
hdu 4374   单调队列+dp
题目大意：一个n层的楼，每层楼有m个格子，每个格子有一定的价值。在每一层楼只能向一个方向走最多走t步，
          开始在顶层的x位置，问到底层的路线上能得到的价值最大。
解题思路：从下往上走，每个状态dp[i][j]为从i层j格子到底层所能得到的最大价值。
          用sum[i][j]表示第i层前j格子的和。
          从左边到j位置的状态转移方程 dp[i][j]=max(dp[i+1][k]+sum[i][j]-sum[i][k-1]);(k+t<=j)。
          上式即为：dp[i][j]=max(dp[i+1][k]-sum[i][k-1])+sum[i][j+1];
          由于max里面包含的项都已知切与j无关。故可以用单调队列，维护单调递增即可。
          其右边的状态转移方程为dp[i][j]=max(dp[i+1][k]+sum[i][k])-sum[i][j-1];(k-t>=j)
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int n,m,x,t,a[105][10005],dp[105][10005],sum[105][10005];
int q[10005],front,rear,ans_l[10005],ans_r[10005];

int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&x,&t))
    {
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                scanf("%d",&a[i][j]);
                sum[i][j]=sum[i][j-1]+a[i][j];
            }
        }
        for(int i=n; i>=1; i--)
        {
            front=0;
            rear=0;
            q[rear++]=1;
            ans_l[1]=1;
            for(int j=2; j<=m; j++)
            {
                while(front<rear&&dp[i+1][q[rear-1]]-sum[i][q[rear-1]-1]<=dp[i+1][j]-sum[i][j-1])
                {
                    rear--;
                }
                q[rear++]=j;
                if(q[front]+t<j)
                    front++;
                ans_l[j]=q[front];
            }
            front=0;
            rear=0;
            q[rear++]=m;
            ans_r[m]=m;
            for(int j=m-1; j>=1; j--)
            {
                while(front<rear&&dp[i+1][q[rear-1]]+sum[i][q[rear-1]]<=dp[i+1][j]+sum[i][j])
                {
                    rear--;
                }
                q[rear++]=j;
                if(q[front]-t>j)
                    front++;
                ans_r[j]=q[front];
            }
            int t1,t2;
            for(int j=1; j<=m; j++)
            {
                t1=dp[i+1][ans_l[j]]+sum[i][j]-sum[i][ans_l[j]-1];
                t2=dp[i+1][ans_r[j]]+sum[i][ans_r[j]]-sum[i][j-1];
                dp[i][j]=max(t1,t2);
            }
        }
        printf("%d\n",dp[1][x]);
    }
    return 0;
}

hdu4374单一队列+dp

相关推荐