ZOJ 3469Food Delivery(区间DP)

Food Delivery


Time Limit: 2 Seconds      Memory Limit: 65536 KB


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 ithperson will gain Bi Displeasure 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 Indexas 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

区间DP

dp[i][j][k] 表示i到j这个区间送完了,快递小哥在哪个端点。

关于区间DP,可以参照这个博客

http://blog.csdn.net/dacc123/article/details/50885903

#include <iostream>
 #include <string.h>
 #include <stdlib.h>
 #include <algorithm>
 #include <math.h>
 #include <stdio.h>

 using namespace std;
 #define MAX 100000000
 int n,v,x;
struct Node
{
    int xi;
    int bi;
}a[1005];
int dp[1005][1005][2];
int cmp(Node a,Node b)
{
    return a.xi<b.xi;
}
int sum[1005];
int main()
{
    while(scanf("%d%d%d",&n,&v,&x)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].xi,&a[i].bi);
        }
         a[n+1].xi=x;a[n+1].bi=0;
        sort(a+1,a+n+2,cmp);
        int pos=0;
        sum[0]=0;
        for(int i=1;i<=n+1;i++)
            sum[i]=sum[i-1]+a[i].bi;
        for(int j=1;j<=n+1;j++)
            if(a[j].xi==x)
                pos=j;
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=n+1;j++)
               dp[i][j][0]=MAX,dp[i][j][1]=MAX;
        dp[pos][pos][0]=0;
        dp[pos][pos][1]=0;
        for(int i=pos;i>=1;i--)
        {
            for(int j=pos;j<=n+1;j++)
            {
                if(i==j)
                    continue;
                int num=sum[i-1]-sum[0]+sum[n+1]-sum[j];
                dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(a[j].xi-a[j-1].xi)*(a[j].bi+num));
                dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(a[j].xi-a[i].xi)*(a[j].bi+num));
                dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(a[i+1].xi-a[i].xi)*(a[i].bi+num));
                dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(a[j].xi-a[i].xi)*(a[i].bi+num));
            }
        }
        printf("%d\n",min(dp[1][n+1][0],dp[1][n+1][1])*v);

    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉战队

在单机上快速、精确的100000类别的检测

今天带来的这篇推送,估计您有读过或试验过,但是为了让更多的科研学者知道这么“牛”的内容知识,接下来就开始说说今天的主题——1000000类的快速精确检测。 注:...

31360
来自专栏小樱的经验随笔

遗传算法详解(LINGO及MatlabGA工具箱求解实现)

遗传算法 1.前言 遗传算法是一种基于生物界自然群体遗传进化机制的自适应全局优化概率搜索算法。它与传统算法不同,不依赖梯度信息,而是通过模拟自然进化过程来搜索最...

2.7K70
来自专栏Crossin的编程教室

身份证号码校验算法

1、数字含义 中国大陆第二代身份证号码由18位数据或字母组成,每位数据都有特定的含义,结果如下: ? 每组数字都有不同的含义: 第1至2位数字代表所在省(直辖市...

61790
来自专栏程序员互动联盟

算法好等同于编程能力强吗?

算法和编程不是同等而言,学好编程包含层面很多,基础的编程语言,良好的逻辑思维能力(算法算是包含在这个层面),编程最核心的是编程思想。 相比而言算法是编程基础里面...

40350
来自专栏开心的学习之路

神经网络体系搭建(一)——神经网络

本篇是神经网络体系搭建的第一篇,解决体系搭建的前四个问题,详见神经网络体系搭建(序) 神经网络 ? 最简单的神经网络 神经网络的定义就不再赘述,直接从最简单的神...

354100
来自专栏应兆康的专栏

强大的位运算

什么是位运算? 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作。比如,and运算本来是一个逻辑运算...

35160
来自专栏MixLab科技+设计实验室

算法驱动型的设计

“Everything should be made as simple as possible, but not simpler” — Albert Eins...

38370
来自专栏MixLab科技+设计实验室

设计中的类比思维与人工智能的图像类比算法

这篇属于论文解读系列,往期写过一篇关于平面设计作品视觉焦点识别的论文解读,本期解读下《Deep Visual Analogy-Making》这篇论文。 ? 有没...

37740
来自专栏Python爬虫与算法进阶

来codewars与我一起玩耍吧

先看一道题目 如何使用代码表示“石头、剪刀、布”之间的关系。 即:石头 > 剪刀,剪刀 > 布, 剪刀 > 布 当时我想了很多,构造一个字典,和数字对应,但是...

378100
来自专栏开心的学习之路

神经网络体系搭建(序)

神经网络这个概念并不陌生,但是从接触到现在这一个月的时间里,云里雾里,始终无法建立起完整的体系,能让自己顺畅地用神经网络解决一个具体问题,并进行有针对性的优化。...

38180

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励