USACO Section 3.1 Score Inflation

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.)

Analysis

This problem seems like a complete package problem, so do it traditionally with some amolaration. As the dynamic function can be writen as f[i][v]=max{f[i-1][v-k*t[i]]+s[i]|0<=k*t[i]<=M}, which aims to calculate the highest score after the choice of the ith problem class within v time. But we can calculate it in a new way.
Traditionally, we calculate it with some for loops:

for (int i=1;i<=N;i++)
    
for (int v=0;v<=M;v++){
        
for (int k=0;k*t[i]<=M;k++){
            
if (max<f[i-1][v-k*t[i]]+s[i]) max=f[i-1][v-k*t[i]]+s[i];
           }

           f[i][v]
=max;
       }
       

Sooner, this algorithm seems too slow for its three for loops and the cost of memories needs a lot. However, it's obvious to see the dynamic funtion is special because the ith situation can only be determined by the last situation: (i-1)th. So, records the result with a 1D array instead of the 2D one to  save memories.
Considering the fact that f[i][0]=0 is really useless, we can later change the 3 for loops into 2 loops and cut boundary. Here I provide the new algorithm:

for (int i=1;i<=N;i++)
    
for (int v=t[i];v<=M;v++)
        f[v]
=max{f[v],f[v-t[i]]+s[i]};

Code

/*
ID:braytay1
PROG:inflate
LANG:C++
*/

#include 
<iostream>
#include 
<fstream>
using namespace std;

int main(){
    ifstream fin(
"inflate.in");
    ofstream fout(
"inflate.out");
    
int N,M;
    fin
>>M>>N;
    
int f[10001];
    
int t[10001],s[10001];
    
for (int i=1;i<=N;i++){
        fin
>>s[i]>>t[i];
    }

    
for (int v=0;v<=M;v++){
        f[v]
=v/t[1]*s[1];
    }

    
for (int i=2;i<=N;i++){
        
int cost;
        cost
=t[i];
        
for (int v=cost;v<=M;v++){
            f[v]
=(f[v]>(f[v-t[i]]+s[i]))?f[v]:(f[v-t[i]]+s[i]);
        }

    }

    fout
<<f[M]<<endl;
    
return 0;
}

posted on 2008-08-20 17:14 幻浪天空领主 阅读(329) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(1)

随笔档案(2)

文章分类(23)

文章档案(22)

搜索

最新评论

阅读排行榜

评论排行榜