当前位置: 首页 > java >正文

信奥赛CSP-J复赛集训(DP专题)(19):P3399 丝绸之路

信奥赛CSP-J复赛集训(DP专题)(19):P3399 丝绸之路

在这里插入图片描述

题目背景

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

题目描述

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

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

  • 移动:向下一个城市进发

  • 休息:呆在原来的城市不动

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

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

输入格式

第一行 2 2 2 个整数 N N N M M M

接下来,连续 N N N 行每行一个整数 D j D_j Dj

连续 M M M 行每行一个整数 C j C_j Cj

输出格式

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

输入输出样例 #1

输入 #1

3 5
10
25
15
50
30
15
40
30

输出 #1

1125

说明/提示

样例解释

1 1 1 天休息。

2 2 2 0 → 1 0\rightarrow 1 01 疲劳值 10 × 30 = 300 10 × 30 = 300 10×30=300

3 3 3 1 → 2 1\rightarrow2 12 疲劳值 25 × 15 = 375 25 × 15 = 375 25×15=375

4 4 4 天休息。

5 5 5 2 → 3 2\rightarrow3 23 疲劳值 15 × 30 = 450 15 × 30 = 450 15×30=450

数据范围

1 ≦ N ≦ M ≦ 1000 1 ≦ N ≦ M ≦ 1000 1NM1000

1 ≦ D i , C i ≦ 1000 1 ≦ D_i , C_i ≦ 1000 1Di,Ci1000

AC代码:

#include<bits/stdc++.h>
using namespace std;
/*思路: 1、dp数组:dp[i][j]含义:前j天走到第i个城市的代价情况一: 第j天在第i个城市休息 dp[i][j]=dp[i][j-1]情况二: 第j天从第i-1个城市到第i个城市dp[i][j]=dp[i-1][j-1]+d[i]*c[j]2、状态转移方程:dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+d[i]*c[j])*/ 
int n,m,d[1010],c[1010],dp[1010][1010]; 
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>d[i];for(int i=1;i<=m;i++) cin>>c[i];//dp初始化memset(dp,0x3f,sizeof(dp));for(int j=0;j<=m;j++) dp[0][j]=0;//用j天走到第0个城市的代价均为0 //递推for(int i=1;i<=n;i++){//城市  for(int j=1;j<=m;j++){//天数  dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+d[i]*c[j]);}} //输出cout<<dp[n][m]; return 0;
} 

文末彩蛋:

关注并查看老师的个人主页,学习完整csp信奥赛完整系列课程: https://edu.csdn.net/lecturer/7901

在这里插入图片描述

http://www.xdnf.cn/news/1171.html

相关文章:

  • 基于51单片机的温度控制系统proteus仿真
  • 客户端 AI 与服务器端 AI 的深度比较及实践建议?
  • 精益数据分析(15/126):解锁数据分析关键方法,驱动业务增长
  • 【数字图像处理】立体视觉信息提取
  • 鸿蒙Flutter仓库停止更新?
  • 深度解析MySQL INSERT ... ON DUPLICATE KEY UPDATE语句
  • 深度学习是什么?该怎么入门学习?
  • 设置开机自启动
  • 深度学习与总结JVM专辑(七):垃圾回收器—CMS(图文+代码)
  • Anaconda 与 Miniconda 的差异详解
  • Windows 下 Git 入门指南:从安装、配置 SSH 到加速 GitHub 下载
  • 文档管理 Document Management
  • YOLO改进实战:添加SOCA注意力机制提升目标检测性能
  • 基于 Electron、Vue3 和 TypeScript 的辅助创作工具全链路开发方案:涵盖画布系统到数据持久化的完整实现
  • 【MCP Node.js SDK 全栈进阶指南】初级篇(4):MCP工具开发基础
  • 【MCP Node.js SDK 全栈进阶指南】初级篇(6):MCP传输层配置与使用
  • Python跨平台桌面应用程序开发
  • 代码随想录第三十七天|华为秋季笔试真题230823
  • CAN节点错误管理机制工作原理解析
  • go语言中defer使用指南
  • flutter_slidable 插件使用
  • w~视觉~3D~合集2
  • Web开发-JavaEE应用JNDI注入RMI服务LDAP服务DNS服务高版本限制绕过
  • 互联网黑灰产攻击分析
  • 联易融出席深圳链主企业供应链金融座谈会,加速对接票交所系统
  • 搜索策略的基本概念
  • 开发网页程序时预览时遇到跨域问题解决方法
  • SCP 命令教程:安全文件传输指南
  • Java八股 深入理解Spring的AOP 面向切面编程 底层 保姆级教程 手写例子
  • vue3+canvas裁剪框样式【前端】