ZOJ - 3469 Food Delivery(区间DP)
发布日期:2021-10-03 15:44:41 浏览次数:1 分类:技术文章

本文共 2527 字,大约阅读时间需要 8 分钟。

题目大意:有一个餐厅,在X这个位置,送餐速度为v的-1次方,有N个顾客,分别在pos位置,每个顾客都有一个displeasure值,当餐送到该顾客手上时,该顾客的displeasure总值为 displeasure值 * 到手时间

问所有顾客的最小displeasure总值和是多少

解题思路:首先按位置排个序

设dp[i][j][0]为[i,j]这个区间内的所有人都拿到货了,送货员最后停在i这个位置的最小displeasure总值和
dp[i][j][1]为[i,j]这个区间内的所有人都拿到货了,送货员最后停在j这个位置的最小displeasure总值和
下面的AllDispleasure表示的是区间之外的所有displeasure值的总和,因为区间外的所有人都还没有拿到货,所以要(AllDispleasure + 目的地的displeasure) * (送货时间)
那么dp[i][j][0] = min( dp[i][j][0] , dp[i + 1][j][0] + (pos[i + 1] - pos[i]) * (AllDiapleasure + displeasure[i]))

dp[i][j][0] = min( dp[i][j][0] , dp[i + 1][j][1] + (pos[j] - pos[i]) * (AllDiapleasure + displeasure[i]))

dp[i][j][1] = min( dp[i][j][1] , dp[i][j - 1][0] + (pos[j] - pos[i]) * (AllDiapleasure + displeasure[j]))

dp[i][j][0] = min( dp[i][j][1] , dp[i][j - 1][1] + (pos[j] - pos[j - 1]) * (AllDiapleasure + displeasure[j]))

最后答案是min(dp[1][n - 1][0], dp[1][n - 1][1]) * v

#include 
#include
#include
using namespace std;const int N = 1010;struct Node{ int pos, b;}node[N];int n, v, start;int Sum[N], dp[N][N][2];bool cmp(const Node &a, const Node &b) { return a.pos < b.pos;}void init() { for (int i = 1; i <= n; i++) scanf("%d%d", &node[i].pos, &node[i].b); n++; node[n].pos = start; node[n].b = 0; n++; sort(node + 1, node + n, cmp); Sum[0] = 0; for (int i = 1; i < n; i++) Sum[i] = Sum[i - 1] + node[i].b;}int Displaysure(int l, int r) { if (l > r) return 0; return Sum[r] - Sum[l - 1]; }void solve() { memset(dp, 0x3f, sizeof(dp)); int startPos; for (int i = 1; i < n; i++) { if (node[i].pos == start) { startPos = i; break; } } dp[startPos][startPos][0] = dp[startPos][startPos][1] = 0; for (int i = startPos; i >= 1; i--) for (int j = startPos; j < n; j++) { if (i == j) continue; int t = Displaysure(1, i - 1) + Displaysure(j + 1, n - 1); dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][0] + (node[i + 1].pos - node[i].pos) * (t + node[i].b)); dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][1] + (node[j].pos - node[i].pos) * (t + node[i].b)); dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][0] + (node[j].pos - node[i].pos) * (t + node[j].b)); dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + (node[j].pos - node[j - 1].pos) * (t + node[j].b)); } printf("%d\n", min(dp[1][n - 1][0], dp[1][n - 1][1]) * v);}int main() { while (scanf("%d%d%d", &n, &v, &start) != EOF) { init(); solve(); } return 0;}

转载地址:https://blog.csdn.net/L123012013048/article/details/48834705 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:ZOJ - 2421 Recaman's Sequence(打表水题)
下一篇:POJ - 1651 Multiplication Puzzle(区间dp)

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月16日 18时16分52秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java 调试dll jna_Java调用dll的实现,JNA框架 | 学步园 2019-04-21
ios php上传视频文件_IOS上传图片 PHP服务器接收并上传 2019-04-21
php redis zrevrange,Redis Zrevrange 命令 2019-04-21
php利用word模板导出excel文件,php生成导出word doc和excel文件实例 2019-04-21
java 边缓存边播放,java动态缓存技术:WEB缓存应用 2019-04-21
php云盘匿名,PHP7之匿名类 2019-04-21
matlab数据大小不兼容,MATLAB无法执行赋值,因为左侧的索引与右侧的大小不兼容。 求解... 2019-04-21
editor.md使用php,editor.md 配置参数和使用方法 2019-04-21
python mod,mod_python的安装 2019-04-21
python分析彩票数据,这波太炸了!Python脚本可视化居然可以这么玩 2019-04-21
简单的mysql重置root密码,重置mysql的root密码最简单的方法 2019-04-21
用matlab仿真mmc环流抑制器,一种基于准PR控制原理的MMC阀组环流抑制方法 2019-04-21
oracle 排序的分析函数,Oracle SQL:使用分析排序函数 2019-04-21
oracle direct for hdfs xi下载,ORACLE连接HDFS有个专项的解决方案 2019-04-21
java 403怎么抛出_java – 如何在Spring MVC中返回403禁止? 2019-04-21
java jsch工具类_Java工具集-JSch连接远程服务器工具类 2019-04-21
cmd背景变红1003无标题_怎样修改cmd中文字的大小、颜色和背景颜色呢 原来是这样的... 2019-04-21
php rand() 重复,php – mt_rand()给我总是相同的数字 2019-04-21
php taglib.php,thinkphp5 taglib自定义标签教程 2019-04-21
java常用包类 array,Java中的StringBuffer和数组Arrays以及常用类型的包装类 2019-04-21