P2430 严酷的训练 题解
2024-09-20 20:15:46
题目背景
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 01背包入门题吧
核心代码:dp[j]=max(dp[j], dp[j-w[i]]+c[i]);反正注意规范一下自己的代码
ac代码如下:
#include<cstdio>
#define MAXN int(5e3+5)
#define max(a, b) (a)>(b)?(a):(b)
int dp[MAXN];
int w[MAXN], c[MAXN];
int time[MAXN];
int main()
{
int n, m, a, b, x, v;
scanf("%d%d", &a, &b);
scanf("%d%d", &n, &m);
for (int i = ; i <= m; ++i)
{
scanf("%d", &time[i]);
time[i] *= (b / a);
}
for (int i = ; i <= n; ++i)
{
scanf("%d%d", &x, &c[i]);
w[i] = time[x];
}
scanf("%d", &v);
for (int i = ; i <= n; ++i)
for (int j = v; j >=w[i]; --j)
dp[j] = max(dp[j], dp[j - w[i]] + c[i]); printf("%d\n", dp[v]);
}
最新文章
- [No000083]文件与文件夹操作
- 关于redis启动流程介绍
- 按下enter键后表单自动提交问题
- [Lintcode 3sum]三数之和(python,二分)
- Netty源码阅读(一) ServerBootstrap启动
- bzoj2333
- 从外国html5网站上扒来一个鼠标经过的css3 效果,感觉很不错
- 拾遗补缺之session,高手请跳过!
- javascript高级知识分析——定义函数
- 【百度地图API】如何制作孪生姐妹地图?
- CCNP-3.vlan间路由及三层交换机的配置
- yii2 源码分析 Component类分析 (二)
- form组件
- memcached-redis
- Java -- JDBC_利用反射及 JDBC 元数据编写通用的查询方法
- hdu 4253(经典题目:二分+最小生成树)
- PDF,word ,PPT,等各种文件转换在线工具(免费)
- Nginx中间件使用心得(三)
- 涉及到【分页】的table的请求模式
- selenium 标签页切换
热门文章
- 动态规划法(八)最大子数组问题(maximum subarray problem)
- SQL 数据库加字段声明
- RowVersion 用法
- webpack4 系列教程(九): CSS Tree Shaking
- python之类与类之间的关系
- Chrome浏览器跨域
- php获取数据库中数据
- [VUE ERROR] Invalid default value for prop ";slides";: Props with type Object/Array must use a factory function to return the default value
- Android FileUtils 文件操作类
- android recovery升级过程中掉电处理