洛谷 P3800 Power收集 题解【DP】【单调队列】

作者: wjyyy 分类: DP,单调队列/单调栈,解题报告 发布时间: 2018-07-06 10:23

点击量:19

 

   区间最大值转移问题。

 

题目背景

据说在红雾异变时,博丽灵梦单身前往红魔馆,用十分强硬的手段将事件解决了。

 

然而当时灵梦在Power达到MAX之前,不具有“上线收点”的能力,所以她想要知道她能收集多少P点,然而这个问题她答不上来,于是她找到了学OI的你。

 

题目描述

可以把游戏界面理解成一个N行M列的棋盘,有K个格子上有P点,其价值为val(i,j)

 

初始灵梦可以选择在第一行的任意一个格子出发,每秒她必须下移一格。

 

灵梦具有一个左右移动的速度T,可以使她每秒向左或右移动至多T格,也可以不移动,并且不能折返。移动可视为瞬间完成,不经过路途上的点,只能获得目标格子的P点。

 

求最终她能获得的POWER值最大是多少?

输入输出格式

输入格式:

第一行四个数字,N,M,K,T;

接下来K行每行3个数字x,y,v,代表第x行第y列有一个val为v的P点,数据保证一个格子上最多只有1个P点。

输出格式:

一个数字,为最大POWER值。

输入输出样例

输入样例#1:
3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3
输出样例#1:
9

说明

对于40%的测试点,1<=N,M,T,K<=200

对于100%的测试点,1<=N,M,T,K<=4000

v<=100,N,M,K,T均为整数

by-szc

 

题解:

   这是一个基础的DP找最值转移问题,不过T的范围和N,M一样大,时间复杂度为\(O(NMT)=O(N^3)\),因此要用单调队列优化。因为相邻的两个点用的状态可能相同,所以在一行开始时把t范围内的点压进去,每个点(i,j)再引入(i-1,j+t),接着判断队首是否满足大于j-t的范围内,不符合则出队。

   这里最好把下标放在队列里,可以用下标来访问值,也可以迅速判断下标是否出界,同时如果要求求出路径,也很方便。

 

Code:

#include<cstdio>
int min(int x,int y)
{
    return x<y?x:y;
}
int v[4040][4040];
int f[4040][4040];
int q[4444],l=0,r=0;
int main()
{
    int n,m,k,t,u,V,w;
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&u,&V,&w);
        v[u][V]=w;
    }
    for(int i=1;i<=n;i++)
    {
        l=0,r=0;
        for(int j=1;j<=t;j++)
        {
            while(l<r&&f[i-1][q[r]]<f[i-1][j])//把所有1-t的入队
                r--;
            q[++r]=j;
        }
        for(int j=1;j<=m;j++)
        {
            if(j+t<=m)//把刚进范围的入队
            {
                while(l<r&&f[i-1][q[r]]<f[i-1][j+t])
                    r--;
                q[++r]=j+t;
            }
            if(q[l+1]<j-t)//不在范围内出队
                l++;
            f[i][j]=f[i-1][q[l+1]]+v[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
        ans=ans>f[n][i]?ans:f[n][i];
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */