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
(Take two problems from #2 and three from #4.)
思路：DP背包，f[m]=max(f[m],f[m-cost[i]]+value[i]);
失误点：原先没仔细思考用了贪心WA了一次。超了一次。这种题真应该一次过
代码：
/* ID:nealgav1 LANG:C++ PROG:inflate*//* ID:nealgav1 LANG:C++ PROG:inflate*/#include<fstream>#include<cstring>#include<algorithm>using namespace std;ifstream cin("inflate.in");ofstream cout("inflate.out");const int mm=11000;int dp[mm];class node{ public: int point,time; float num; /*bool operator <(node a,node b) { return a.num>b.num; }*/}f[mm];bool cmp(node a,node b){ return a.num>b.num;}int main(){ int time,cas; cin>>time>>cas; memset(dp,0,sizeof(dp)); for(int i=0;i<cas;i++) {cin>>f[i].point>>f[i].time;} //sort(f,f+cas,cmp); int sum=0; /**DP背包*/ for(int i=0;i<cas;i++) {for(int k=f[i].time;k<=time;k++) if(k-f[i].time>=0) dp[k]=max(dp[k],dp[k-f[i].time]+f[i].point); } cout<<dp[time]<<"\n";}/**#include<fstream>#include<algorithm>using namespace std;ifstream cin("inflate.in");ofstream cout("inflate.out");const int mm=11000;class node{ public: int point,time; float num;}f[mm];bool cmp(node a,node b){ return a.num>b.num;}int main(){ int time,cas; cin>>time>>cas; for(int i=0;i<cas;i++) {cin>>f[i].point>>f[i].time;f[i].num=(float)f[i].point/(float)f[i].time;} sort(f,f+cas,cmp); int sum=0; for(int i=0;i<cas;i++) { int n=time/f[i].time; time-=n*f[i].time; sum+=n*f[i].point; } cout<<sum<<"\n";}*/
Score Inflation
Russ Cox
We use dynamic programming to calculate the best way to use t minutes for all t from 0 to tmax.
When we find out about a new category of problem with points p and length t, we update the best for j minutes by taking the better of what was there already and what we can do by using a p point problem with the best for time j - t.
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h>#define MAXCAT 10000#define MAXTIME 10000int best[MAXTIME+1];voidmain(void){ FILE *fin, *fout; int tmax, ncat; int i, j, m, p, t; fin = fopen("inflate.in", "r"); fout = fopen("inflate.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d %d", &tmax, &ncat); for(i=0; i<ncat; i++) { fscanf(fin, "%d %d", &p, &t); for(j=0; j+t <= tmax; j++) if(best[j]+p > best[j+t]) best[j+t] = best[j]+p; } m = 0; for(i=0; i<=tmax; i++) if(m < best[i]) m = best[i]; fprintf(fout, "%d\n", m); exit(0);}
Greg Price writes: After the main `for' loop that does the actual DP work, we don't need to look at the entire array of best point totals to find the highest one. The array is always nondecreasing, so we simply output the last element of the array.
#include <fstream.h>ifstream fin("inflate.in");ofstream fout("inflate.out");const short maxm = 10010;long best[maxm], m, n;voidmain(){ short i, j, len, pts; fin >> m >> n; for (j = 0; j <= m; j++) best[j] = 0; for (i = 0; i < n; i++) { fin >> pts >> len; for (j = len; j <= m; j++) if (best[j-len] + pts > best[j]) best[j] = best[j-len] + pts; } fout << best[m] << endl; // This is always the highest total.