ZOJ - 3469 Food Delivery(区间DP)-程序员宅基地

Time Limit: 2000MS
Memory Limit: 65536KB
64bit IO Format: %lld & %llu

Status

Description

When we are focusing on solving problems, we usually prefer to stay in front of computers rather than go out for lunch. At this time, we may call for food delivery.

Suppose there are N people living in a straight street that is just lies on an X-coordinate axis. The ith person's coordinate is Xi meters. And in the street there is a take-out restaurant which has coordinates X meters. One day at lunchtime, each person takes an order from the restaurant at the same time. As a worker in the restaurant, you need to start from the restaurant, send food to the N people, and then come back to the restaurant. Your speed is V-1 meters per minute.

You know that the N people have different personal characters; therefore they have different feeling on the time their food arrives. Their feelings are measured by Displeasure Index. At the beginning, the Displeasure Index for each person is 0. When waiting for the food, the ith person will gain BiDispleasure Index per minute.

If one's Displeasure Index goes too high, he will not buy your food any more. So you need to keep the sum of all people's Displeasure Index as low as possible in order to maximize your income. Your task is to find the minimal sum of Displeasure Index.

Input

The input contains multiple test cases, separated with a blank line. Each case is started with three integers N ( 1 <= N <= 1000 ), V ( V > 0), X ( X >= 0 ), then N lines followed. Each line contains two integers Xi ( Xi >= 0 ), Bi ( Bi >= 0), which are described above.

You can safely assume that all numbers in the input and output will be less than 231 - 1.

Please process to the end-of-file.

Output

For each test case please output a single number, which is the minimal sum of Displeasure Index. One test case per line.

Sample Input

5 1 0
1 1
2 2
3 3
4 4
5 5

Sample Output

55


题意:在X-轴上有一个餐厅,以及有n个点要送外卖。

餐厅坐标为x。工人的速度为V-1。也就是 1/v 米每分钟(不是v米每分钟)。给出n的点的x坐标和參数v,外卖没送到,客户就会不愉快。每一分钟的不愉快指数添加v。问怎么样的送货策略。使得全部客户的总不愉悦指数和最小。


思路:区间DP。用一个数组 dp 维护。

DP的思路就是。假设要訪问完 [i, j] ,那么它的子区间一定訪问完了。


dp[i][j][0] 表示当前 [ i, j ] 区间内已经所有送餐完成,而且这个时刻工人位于区间左端。也就是坐标 i

dp[i][j][1] 表示当前 [ i, j ] 区间内已经所有送餐完成,而且这个时刻工人位于区间又端,也就是坐标 j

状态转移方程:

以餐厅的位置 pos 为中间点,i 在餐厅pos位置的左边,j 在餐厅pos位置的右边。

dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][0]+(a[i+1].x-a[i].x)*(delay+a[i].v));

这个方程里面,delay 表示区间 [i,j] 之外的全部点的v值之和。a[i+1].x-a[i].x 表示距离。dp[i+1][j][0]是已经求出来的子区间,加上(a[i+1].x-a[i].x)*(delay+a[i].v))。就得到 dp[i][j][0]。



#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

const int INF = 1<<29;
const double PI = acos(-1.0);
const double e = 2.718281828459;
const double eps = 1e-8;
const int MAXN = 1010;
int dp[MAXN][MAXN][2];
int sum[MAXN];
struct node
{
    int x;
    int v;
} a[MAXN];

int cmp(node x, node y)
{
    return x.x < y.x;
}

int Delay(int l, int r)
{
    if(l > r)
        return 0;
    return sum[r]-sum[l-1];
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n, v, x;
    while(scanf("%d %d %d", &n, &v, &x) != EOF)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d %d", &a[i].x, &a[i].v);
        n++;
        a[n].x = x;
        a[n].v = 0;
        sort(a+1, a+1+n, cmp);
        sum[0] = 0;
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i-1]+a[i].v;
        int pos = 1;
        for(int i = 1; i <= n; i++)
        {
            if(a[i].x == x)
            {
                pos = i;
                //cout<<pos<<endl;
                break;
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j][0] = dp[i][j][1] = INF;
            }
        }
        dp[pos][pos][0] = dp[pos][pos][1] = 0;
        for(int i = pos; i >= 1; i--)
        {
            //i循环pos左边
            for(int j = pos; j <= n; j++)
            {
                //j循环pos右边
                int delay = Delay(1, i-1)+Delay(j+1, n);
                if(i == j)
                    continue;
                dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][0]+(a[i+1].x-a[i].x)*(delay+a[i].v));
                dp[i][j][0] = min(dp[i][j][0], dp[i+1][j][1]+(a[j].x-a[i].x)*(delay+a[i].v));
                dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][0]+(a[j].x-a[i].x)*(delay+a[j].v));
                dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][1]+(a[j].x-a[j-1].x)*(delay+a[j].v));
            }
        }
        printf("%d\n", min(dp[1][n][0], dp[1][n][1])*v);
        //本题的v一定要留到后面来乘,中间DP的时候乘可能会溢出,导致wa
    }
    return 0;
}



转载于:https://www.cnblogs.com/gavanwanggw/p/7274008.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_33738578/article/details/94730686

智能推荐

Eclipse中项目Src看不到.Java文件_eclipse导入的项目src下没java-程序员宅基地

文章浏览阅读5.2k次。Eclipse中项目Src看不到.Java文件需要从Java切换到java EE 工作空间_eclipse导入的项目src下没java

Linux C函数之文件及目录函数(全)_c语言 getwd-程序员宅基地

文章浏览阅读677次。转载地址:http://blog.sina.com.cn/s/blog_695e489c01013ldd.html【转】Linux C函数之文件及目录函数(全)(2012-03-30 17:17:37)转载▼标签:杂谈分类: c语言学习chdir, chmod, chown, chroot_c语言 getwd

ie6,ie7,ie8 css bug兼容解决记录_style clor #fff-程序员宅基地

文章浏览阅读769次。断断续续的在开发过程中收集了好多的bug以及其解决的办法,都在这个文章里面记录下来了!希望以后解决类似问题的时候能够快速解决,也希望大家能在留言里面跟进自己发现的ie6 7 8bug和解决办法!1:li边距“无故”增加任何事情都是有原因的,li边距也不例外。先描述_style clor #fff

HDMI信号电平波形_hdmi信号波形-程序员宅基地

文章浏览阅读9.4k次,点赞6次,收藏39次。HDMI1.4 信号解析说明1、HDMI1.4接口相关引脚说明如下图所示,3组数据差分信号,1组时钟差分信号,I2C,CEC,HOTPLUG,电源和GND; 注:1)HOTPLUG脚在未连接从设备时为低电平,连接后会变成高电平,连接过程中强制给HOTLUG脚发100ms低电平系统会重新进行HDMI连接; 2)HDMI_I2C接口用于主设备和从设备间EDID信息和HDCP认证交互。2、接口中各引脚电平的高值如下表所示:NO. PIN ..._hdmi信号波形

python实现stack(栈)和队列(queue)_python stack queue-程序员宅基地

文章浏览阅读9.7k次,点赞4次,收藏28次。栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于: stack:后进先出 栈示意图queue:先进先出 队列示意图 注意,stack和queue是没有查询具体某一个位置的元素的操作的。但是他们的排列是按顺序的对于stack我们可以使用python内置的list实现,因为list是属于线性数组,在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求。_python stack queue

纠正:Android RecyclerView滚动到指定位置并置顶(滚动方法、移动置顶、定位滑动到指定位置item)_groupedrecyclerviewadapter跳到指定item-程序员宅基地

文章浏览阅读3.1w次,点赞61次,收藏107次。最近博主发现让RecyclerView滑动到某一位置并置顶的博客一大堆,抄的是完全一模一样。此外,虽然这些博客“解决”了这些问题,但这种解决方案过于浅显、粗暴,甚至都违背了开发思想。遂在此纠正这种错误。RecyclerView提供了几种移动的方法scrollToPositionscrollToscrollBysmoothScrollBysmoothScrollToPosit..._groupedrecyclerviewadapter跳到指定item

随便推点

Maven1-配置及创建JavaSE项目_maven 创建javase工程-程序员宅基地

文章浏览阅读431次。一、Maven简介项目构建工具(不只是管理jar包),项目设计和编码由程序员来做,它做不了;而编译,运行,测试,打包,部署,jar管理它都能做Apache提供,Java开发的,运行Maven要有基本的java开发工具包Maven仓库:存储jar包本地仓库:当前本地电脑远程仓库:局域网中的服务器中央仓库:远程服务器有远程仓库:本地连接远程,远程仓库中有就下载到本地,没有就去连中央仓库,中央仓库下载到远程,远程再下载到本地,适合团队开发,远程仓库可以连接多个本地仓库,所以很多公_maven 创建javase工程

【转载】FPGA配置方式_quartus烧录-程序员宅基地

文章浏览阅读6.3k次,点赞2次,收藏31次。【概要】FPGA配置方式首先介绍下AS、PS、JTAG三种模式的区别。AS模式: 主动串行配置模式。将.pof文件烧写到flash(掉电不丢失)芯片,FPGA器件每次上电时,作为主控制器从配置器件flash(EPCS)主动读取程序文件并存放至FPGA内部的配置存储器(configure RAM),实现逻辑运作,该方法适用于不需要经常升级的场合,一次性读取程序文件;PS..._quartus烧录

GitHub集成Circle CI(附 Circle CI 配置示例文件)_circleci building status github-程序员宅基地

文章浏览阅读1.6k次。文章目录GitHub 集成Circle CICI(持续集成) 简单解释CI 工具Circle的使用将GitHub项目授权给 Circle CI书写 config.yml文件测试 Circle CI 配置文件是否生效备注写在最后GitHub 集成Circle CICI(持续集成) 简单解释CI 即 Continuous Integration. 当代码提交上来有变动的时候,在merge之前自动进行一些流程,如:代码风格检查、单元测试是否通过等。当被merge之后,又会自动进行一些流程,如:自动打包、_circleci building status github

matlab题目如何在一个圆形区域进行三维作图_meshgrid ,边界是圆-程序员宅基地

文章浏览阅读3.2k次,点赞3次,收藏7次。不废话上图[r,t]=meshgrid(0:0.1:2,0:0.02:2*pi);x=r.*cos(t);y=r.*sin(t);z=x.^2+y.^2;mesh(x,y,z)其实在数学上使用了一个圆的参数方程来实现绘制区域为圆形的效果在这个区域上面是一个碗状图形_meshgrid ,边界是圆

jwt token注销_如何用SpringBoot集成JWT实现token验证及token注销?一招教会你-程序员宅基地

文章浏览阅读763次。Json web token (JWT), 是为了在网络应用环境间传递声明而执行的一种基于JSON的开放标准((RFC 7519).定义了一种简洁的,自包含的方法用于通信双方之间以JSON对象的形式安全的传递信息。因为数字签名的存在,这些信息是可信的,JWT 可以使用HMAC算法或者是RSA的公私秘钥对进行签名。JWT 请求流程这里还要注意:光理论是不够的。在此顺便送大家十套20..._springboot jwt 注销登陆

Lock锁的使用-程序员宅基地

文章浏览阅读1.6w次,点赞25次,收藏108次。在Java多线程中,可以使用synchronized关键字实现线程之间的同步互斥,在jdk1.5后新增的ReentrantLock类同样可达到此效果,且在使用上比synchronized更加灵活。观察ReentrantLock类可以发现其实现了Lock接口public class ReentrantLock implements Lock,java.io.Serializable1、使用Re..._lock锁的使用