P3399 丝绸之路

题目背景

张骞于公元前138年曾历尽艰险出使过西域。加强了汉朝与西域各国的友好往来。从那以后,一队队骆驼商队在这漫长的商贸大道上行进,他们越过崇山峻岭,将中国的先进技术带向中亚、西亚和欧洲,将那里的香料、良马传进了我国。每当人们凝望荒凉的大漠孤烟,无不引起对往日商贸、文化繁荣的遐想……

题目描述

小仓鼠带着货物,从中国送到安息,丝绸之路包括起点和终点一共有N+1个城市,0号城市是起点长安,N号城市是终点巴格达。要求不超过M天内必须到达终点。一天的时间可以从一个城市到连续的下一个城市。从i-1城市到i城市距离是Di。

大家都知道,连续赶路是很辛苦的,所以小仓鼠可以在一个城市时,可以有以下选择:

  • 移动:向下一个城市进发
  • 休息:呆在原来的城市不动

沙漠天气变化无常,在天气很不好时,前进会遇到很多困难。我们把M天的第j(1<=j<=M)天的气候恶劣值记为Cj。从i-1城市移动到i城市在第j天进发时,需要耗费Di*Cj的疲劳度。

不过小仓鼠还是有选择权的,可以避开比较恶劣的天气,休息是不会消耗疲劳值的。现在他想知道整个行程最少要消耗多少疲劳值。

输入输出格式

输入格式:

第一行2个整数N,M

连续N行每行一个整数Dj

连续M行每行一个整数Cj

输出格式:

一个整数,表示最小疲劳度

输入输出样例

输入样例#1:

3 5
10
25
15
50
30
15
40
30

输出样例#1:

1125

说明

本题时限1s,内存限制128M,因新评测机速度较为接近NOIP评测机速度,请注意常数问题带来的影响。

第1天休息

第2天0->1 疲劳值 10 × 30 = 300 .

第3天1->2 疲劳值 25 × 15 = 375 .

第4天休息

第5天2->3 疲劳值 15 × 30 = 450 .

1 ≦ N ≦ M ≦ 1000

1 ≦ Di , Ci ≦ 1000

用dp[i][j]表示走到第i个城市,第j+1天的时候的疲劳值的最小值;

决策在题目里说的很清楚。

(代码不是我写的,但是大体思路是一样的,我写的那份因为特殊原因不小心丢了。。、)

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int n,m,d[1001],c[1001],dp[1001][1001];
 5 int main()
 6 {
 7     cin >> n >> m;
 8     for(int i=1;i<=n;i++)
 9         cin >> d[i];
10     for(int i=1;i<=m;i++)
11         cin >> c[i];
12     memset(dp,0x3f,sizeof(dp));
13     memset(dp[0],0,sizeof(dp[0]));
14     for(int i=1;i<=n;i++)
15         for(int j=1;j<=m;j++)
16             dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+d[i]*c[j]);
17     cout << dp[n][m] << endl;
18     return 0;
19 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联资讯

“没有中国茶只有龙德记”为实,“怒掷酒瓶振国威”为虚

1915年巴拿马万国博览会共颁25527个奖!中国拿到了1200多个,茅台只是获得第四等级的奖,其"怒掷酒瓶振国威"故事更是毫无根据的事。

1921
来自专栏新智元

2016年 CES 大展 VR/AR 论坛前瞻

国外 VR 媒体uploadvr最近收集整理了即将举行的 16年CES 大展上,VR/AR 部分的论坛安排。我们一起来看看。本文分两部分,按日期,上部分是 1月...

3668
来自专栏互联资讯

震撼穿越“亿年壶穴、天地奇观”!无人机成功穿越白云山亿年大壶穴!

福安白云山是史志记载的“闽东第一山”。因四季云雾缭绕,弥望如海,故名白云山。说起闽东宁德的风景,大家都不由想起太姥山和白水洋。可大家知道吗?福建福安白云山、屏南...

1404
来自专栏云市场·精选汇

云蚁万能门店小程序解决方案

旅游门票:高密龙行天下旅行社、洛阳燕行天下旅行社、西安市旅游攻略、海南逍遥游、日照旅游指南

30711
来自专栏PPV课数据科学社区

穿越5000英里去见系统推荐好友,这是大数据的威力

曾经为了 去看我的女孩 我翻山越岭 不分黑夜白昼 如今却是为了一个爷们 。。。 寻人 Search 在天朝的西方,有一个遥远的国度。那里的人们很傲娇,不用微博用...

2964
来自专栏机器学习和数学

[编程经验] 拉勾网爬虫数据的后续处理

上一篇我们介绍了如何爬拉勾的数据,这次介绍一下如何分析爬下来的数据,本文以自然语言处理这个岗位为例。 上次那个爬虫的代码有一点问题,不知道大家发现没有,反正也没...

9418
来自专栏Java帮帮-微信公众号-技术文章全总结

【非技术面试】面试仪表你必须要注意

面试仪表你必须要注意 面试整体情况总结: 第一, 一定要展现出自己积极向上的精神面貌,服装要简洁、简单、大方。整洁就是整齐和干净,面试时穿着的服装必须是熨烫过或...

3374
来自专栏一个会写诗的程序员的博客

黑客的价值观The Hacker’s Code

黑客,可能在大家的眼里是那些入侵别人计算机搞破坏的人,其实并不是那样的。如果你这样认为了,只能说明你对计算机文化并不了解,真正的黑客是一种 自由的象征,他们挑战...

1002
来自专栏人称T客

问题疫苗高分评标 问责的不能仅限企业

故事总是惊人的相似,曾经的三鹿,今天的长生,从奶粉到疫苗,目标群体都发生在孩童身上,一时间群情激忿,刘强东怒了,因为他的孩子也在问题疫苗之列,还有人说安监局、食...

1620
来自专栏PPV课数据科学社区

大数据视角下的春运迁徙图 来看看你的城市的迁徙半径

今年春节期间,百度做了一个可视化很高的专题【百度迁徙】,讲春运期间各地区的人口迁徙情况。动态图,图很漂亮,也很直观。前两天我在微博分享了9张主要地区的迁徙图,反...

4724

扫码关注云+社区

领取腾讯云代金券