1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

解题思路

本题是一个变形的背包问题:每个包裹可以选择两种“花费”(燃料),其中一种会额外消耗 1 张通行证。目标是先最大化派送包裹数,在此基础上最小化燃料消耗,并满足燃料 ≤ X、通行证 ≤ Y。

算法:动态规划(DP,二元约束下的最优化-可行性分离)

  • 设计状态: 设 dp[j][k] 表示在处理若干包裹后,恰好派送 j 个包裹、使用 k 张通行证时的最小燃料。 初始化:dp[0][0] = 0,其余为正无穷。

P3898.第1题-星际快递

    1000ms Tried: 46 Accepted: 16 Difficulty: 5 所属公司 : 京东
    算法与标签>动态规划

题目内容

星际快递公司有 NNN 个包裹需要派送,每个包裹有两种派送方式!

1、常规派送(消耗较多燃料)

2、虫洞派送(使用一个虫洞通行证,可以以消耗较少燃料的情况下完成派送)

当前快递飞船携带了 XXX 单位的燃料和 YYY 张虫洞通行证。

星际快递公司想要计算,在优先派送尽可能多包裹的情况下,最小的燃料消耗是多少,请你帮助他们计算一下。

输入描述

第一行三个整数 N,X,YN,X,YN,X,Y ,分别表示包裹数量,携带燃料量以及通行证数量。

接下来 NNN 行,每行两个整数,表示各个包裹常规派送和虫洞派送分别需要的燃料量

1≤N≤100,1≤X≤5000,1≤Y<501≤N≤100,1≤X≤5000,1≤Y<501≤N≤100,1≤X≤5000,1≤Y<50 ,每个包裹常规派送和虫洞派送的燃料消耗均介于 [1,50][1,50][1,50] 之间

输出描述

一行,两个整数,空格分开,表示最多可派送的包裹数量及对应的最小燃料消耗。

样例1

输入

3 20 1
8 5
7 4
10 6

输出

2 12

样例2

输入

4 25 2
10 6
8 5
12 7
9 6

输出

3 20

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 2, 62ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?