The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.
We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.
The input includes the length of the contest, M (1 <= M <= 10,000) (don't worry, you won't have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.
Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).
Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.
PROGRAM NAME: inflate
INPUT FORMAT
Line 1: | M, N -- contest minutes and number of problem classes |
Lines 2-N+1: | Two integers: the points and minutes for each class |
SAMPLE INPUT (file inflate.in)
300 4 100 60 250 120 120 100 35 20
OUTPUT FORMAT
A single line with the maximum number of points possible given the constraints.
SAMPLE OUTPUT (file inflate.out)
605
(Take two problems from #2 and three from #4.)
题意:
给出 M(1 ~ 10000),N(1 ~ 10000),代表时间限制是 M ,给出 N 个题目类型。后给出这 N 个题目类型的分数和时间,选择答题类型可以无限次,问在规定时间内如何选取类型使得最后得到的分数最高。
思路:
完全背包。
AC:
/* TASK:inflate LANG:C++ ID:sum-g1 */ #include <cstdio> #include <algorithm> #include <cstring> #define MAX 10005 using namespace std; typedef long long ll; int t[MAX], w[MAX]; ll dp[MAX]; int main() { freopen("inflate.in", "r", stdin); freopen("inflate.out", "w", stdout); int m, n; scanf("%d%d", &m, &n); for (int i = 1; i <= n; ++i) scanf("%d%d", &w[i], &t[i]); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; ++i) for (int j = t[i]; j <= m; ++j) dp[j] = max(dp[j - t[i]] + w[i],dp[j]); printf("%lld\n",dp[m]); return 0; }
相关推荐
Inflation Note
Monetary Policy,Inflation and the business cycle(2015版)PDF
A special focus here is devoted to the pricing of inflation-linked derivatives. The three final new chapters of this second edition are devoted to credit. Since Credit Derivatives are ...
宏观经济学教学课件
US inflation reaccelerated strongly.pdf
JPM (20210505) Positioning for Inflation.pdf
Moss, I. - Quantum Theory, Black Holes, and Inflation
5-year-breakeven-inflation-rate_metadata.json 10-year-breakeven-inflation-rate_metadata.json 10-year-breakeven-inflation-rate_metadata_1.json 20-year-breakeven-inflation-rate_metadata.json 30-year...
数据集包含关于美国五年期...5-year-treasury-inflation-indexed-security-constant-maturity_metadata.json 5-year-treasury-inflation-indexed-security-constant-maturity_metadata_1.json DFII5.csv FII5.csv
Ülke, V.... A comparison of time series and machine learning models for inflation forecasting: Empirical evidence from the USA. Neu- ral Computing and Applications, 30 (5), 1519–1527 .
这是由美联储经济数据库(FRED)托管的美联储数据集。 7-year-treasury-inflation-indexed-security-constant-maturity_metadata.json DFII7.csv
这是由美联储经济数据库(FRED)托管的美联储数据集。FRED有一个数据平台,它们根据数据更新的频率来更新其信息。...30-year-treasury-inflation-indexed-security-constant-maturity_metadata.json DFII30.csv
inflation-vs-unemployment
这是由美联储经济数据库(FRED)托管的圣路易斯...5-year-5-year-forward-inflation-expectation-rate_metadata.json 5-year-5-year-forward-inflation-expectation-rate_metadata_1.json T5YIFR.csv T5YIFRM.csv
基于所有TIPS的未加权平均投标收益率,剩余期限超过10年。这是由美联储经济数据库(FRED)托管的美联储数据集。 DLTIIT.csv treasury-inflation-indexed-long-term-average-yield_metadata.json
这是由美联储经济数据库(FRED)托管的美联储数据集。FRED有一个数据平台,它们根据数据更新的频率来更新其信息。...20-year-treasury-inflation-indexed-security-constant-maturity_metadata.json DFII20.csv
An approach to achieving optimized complex sheet inflation under constraints
基于亲和传播和领域扩散的功能模块识别算法,聂蕊楠,骆嘉伟,转录因子(TF)和microRNA(miRNA)共同调节基因表达,发生扰动可导致人体系统故障和疾病发生。因此,识别miRNA-TF-mRNA共调控模块(CRM)可以
Development of adaptive pneumatic tourniquet systems based on minimal inflation pressure for upper limb surgeries
Inflation.jl:用于宇宙膨胀模型数值评估的Julia软件包。 运输方法解决了摄动问题。 支持任意数量的字段,任意字段空间度量和任意初始条件