P2430 严酷的训练

    • 170通过
    • 285提交
  • 题目提供者jzqjzqjzq
  • 标签 动态规划,动规,dp
  • 难度 普及-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    Lj的朋友WKY是一名神奇的少年,在同龄人之中有着极高的地位。。。

    题目描述

    他的老师老王对他的程序水平赞叹不已,于是下决心培养这名小子。

    老王的训练方式很奇怪,他会一口气让WKY做很多道题,

    要求他在规定的时间完成。

    而老王为了让自己的威信提高,自己也会把这些题都做一遍。

    WKY和老王都有一个水平值,他们水平值的比值和做这些题

    所用时间的比值成反比。比如如果WKY的水平值是1,老王的水平值是2

    那么WKY做同一道题的时间就是老王的2倍。

    每个题目有他所属的知识点,这我们都知道,

    比如递归,动归,最短路,网络流……

    在这里我们不考虑这些事情,我们只知道他们分别是知识点1,知识点2……

    每一个知识点有他对应的难度,比如动态规划经常难于模拟……

    而每一个同一知识点下的题目,对于WKY来讲,都是一样难的。

    而做出每一道题,老王都有其独特的奖励值。

    而奖励值和题目的知识点没有必然联系。

    现在WKY同学请你帮忙,计算

    在老王规定的时间内,

    WKY所能得到最大奖励值是多少 。

    输入输出格式

    输入格式:

    输入文件包括以下内容:

    第一行:

    WKY的水平值和老王的水平值。

    数据保证WKY的水平值小于老王的水平值(哪怕它不现实),

    且老王的水平值是WKY的水平值的整数倍。

    第二行:

    题目的总数m和知识点的总数n。

    第三行:

    n个整数。第i个整数表示 老王在做第i个知识点的题目所需的时间。

    接下来有m行数每一行包括两个整数p,q。

    p表示该题目所属的知识点,q表示该题目对应的奖励值。

    最后一行是规定的时间。

    输出格式:

    输出文件只有一行,表示能到得到的最大奖励值。

    输入输出样例

    输入样例#1: 复制
    1 2
    
    6 4
    
    1 2 3 4
    
    1 5
    
    2 6
    
    3 3
    
    4 8
    
    3 3
    
    4 5
    
    20
    输出样例#1: 复制
    22

    说明

    对于100%的数据,题目总数<=5000,规定时间<=5000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。