HDU-2490-Parade

ACM模版

描述

题解

这个题是需要用单调队列优化优化的动态规划问题,好多 OJOJ 上都有,其中 POJPOJ 数据比较强,需要用输入外挂,并且开 G++G++ 才能过。

dp[i][j]dp[i][j] 表示从最北边到第 ii 行第 jj 列的最大高兴值,很容易想就是枚举前一行状态进行转移,但是会超时,所以我们只需要利用单调队列来维护一下即可,具体的思路请参考 林燕同学的博客,这都是套路……愿区域赛少一些套路,多一些真诚~~~

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int MAXN = 111;
const int MAXM = 1e4 + 10;

int n, m, k;
int sum[MAXM];
int dp[MAXN][MAXM];
int wel[MAXN][MAXM];
int len[MAXN][MAXM];

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0;   //  EOF
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

struct node
{
    int hap, dis;

    node() {}
    node(int h, int d) : hap(h), dis(d) {}
};

int main()
{
    while (~scanf("%d%d%d", &n, &m, &k) && n + m + k)
    {
        ++n;
        memset(dp, 0, sizeof(dp));
        memset(len, 0, sizeof(len));
        memset(wel, 0, sizeof(wel));

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scan_d(wel[i][j]);
            }
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scan_d(len[i][j]);
            }
        }

        for (int i = 1; i <= n; i++)
        {
            deque<node> deq;
            int dis = 0;
            for (int j = 1; j <= m; j++)
            {
                sum[j] = sum[j - 1] + wel[i][j];
            }

            for (int j = 0; j <= m; j++)
            {
                dis += len[i][j];
                while (!deq.empty() && deq.front().hap <= dp[i - 1][j] - sum[j])
                {
                    deq.pop_front();
                }
                deq.push_front(node(dp[i - 1][j] - sum[j], dis));
                while (!deq.empty() && deq.front().dis - deq.back().dis > k)
                {
                    deq.pop_back();
                }
                dp[i][j] = deq.back().hap + sum[j];
            }

            deq.clear();
            dis = 0;
            len[i][m + 1] = 0;
            for (int j = m; j >= 0; j--)
            {
                dis += len[i][j + 1];
                while (!deq.empty() && deq.front().hap <= dp[i - 1][j] + sum[j])
                {
                    deq.pop_front();
                }
                deq.push_front(node(dp[i - 1][j] + sum[j], dis));
                while (!deq.empty() && deq.front().dis - deq.back().dis > k)
                {
                    deq.pop_back();
                }
                dp[i][j] = max(dp[i][j], deq.back().hap - sum[j]);
            }
        }

        int ans = 0;
        for (int j = 0; j <= m; j++)
        {
            ans = max(ans, dp[n][j]);
        }
        printf("%d\n", ans);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python

Django admin 一些有用的设置

Django自带的后台管理是Django明显特色之一,可以让我们快速便捷管理数据。后台管理可以在各个app的admin.py文件中进行控制。以下是我最近摸索总结...

60670
来自专栏V站

Knowledge丨WordPress数据库文件分析

折腾WordPress必须要有很厚的基础才行,深入更是要小心。西顾再次mark下来知更鸟的文章,做下笔记。想研究模板,可review下前文《Skill丨Word...

23740
来自专栏腾讯移动品质中心TMQ的专栏

Android手机上用户操作模拟方法的研究与实现

一、 问题背景 最近研究了一下Android手机上用户操作的模拟方法, 有一些心得与大家分享下。 之所以去研究Android手机上用户操作的模拟方法,是因为最...

1.3K60
来自专栏人工智能LeadAI

在NVIDIA Jetson TX2上安装TensorFlow

刷机的目的是把Ubuntu操作系统和JetPack SDK安装到Jetson TX2上。刷机的操作按照官方教程即可,比较容易。这个过程中有一点需要注意:Jets...

38220
来自专栏Deep learning进阶路

caffe随记(四) --- mnist示例超详细讲解

这个mnist手写体数字识别的例子可以说是caffe中的 Hello World。mnist最初用于支票上的手写数字识别,针对mnist识别的专门模型是Lene...

28900
来自专栏开源优测

基于Excel参数化你的Selenium2测试

前言 今天我们就如何使用xlrd模块来进行python selenium2 + excel自动化测试过程中的参数化进行演示说明,以解决大家在自动化测试实践过程中...

29340
来自专栏Linux内核

Linux OOM机制分析

oom_killer(out of memory killer)是Linux内核的一种内存管理机制,在系统可用内存较少的情况下,内核为保证系统还能够继续运行下去...

1.4K70
来自专栏大数据-Hadoop、Spark

Hadoop CombineTextInputFormat的使用

15530
来自专栏ml

catalan---卡特兰数(小结)

(关于卡特兰数的详细介绍)http://baike.baidu.com/view/2499752.htm 下面有练习的题目: 经过测试,_int64/long...

41970
来自专栏乐沙弥的世界

Oracle RAC OCR 的备份与恢复

        Oracle Clusterware把整个集群的配置信息放在共享存储上,这些信息包括了集群节点的列表、集群数据库实例到节点的映射以及CRS应用...

13320

扫码关注云+社区

领取腾讯云代金券