Score Inflation
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
题意：
给出比赛最大时间M及比赛题目类型数目N。每种题目类型里可以有无数个题目。接下来N行，给出每种题目类型里一个题目的分数
和限定时间。要求在满足总时间M的情况下，能使得分数最多的题目安排。
代码如下：
/*
LANG: C
TASK:inflate
*/
#include<stdio.h>
#define nmax 10001
int score[nmax];
int main()
{
freopen("inflate.in", "r", stdin);
freopen("inflate.out", "w", stdout);
int n, m, i, j, s, t;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
{
score[i] = 0;
}
for (i = 0; i < m; i++)//[i, j]表示前i+1种类型的题中，时间为j得到的最大分数
{
scanf("%d%d", &s, &t);
for (j = t; j <= n; j++)//因为对每种类型。取一题就需要t时间。所以可以从t开始。
{
if (score[j] < score[j - t] + s)
{
score[j] = score[j - t] + s;
}
}
}
printf("%d\n", score[n]);
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}