• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 幻浪天空領(lǐng)主 閱讀(344) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            伊人久久五月天| 狠狠色丁香婷婷久久综合不卡| 久久婷婷国产麻豆91天堂| 国产精品美女久久久久网| Xx性欧美肥妇精品久久久久久| 国产99久久九九精品无码| 久久综合亚洲色一区二区三区| 亚洲国产精品无码久久久不卡 | 久久频这里精品99香蕉久| 色欲久久久天天天综合网| 狠狠狠色丁香婷婷综合久久俺| 久久久久亚洲AV无码去区首| 伊人久久大香线蕉综合影院首页| av无码久久久久不卡免费网站| 国产精品综合久久第一页| 囯产精品久久久久久久久蜜桃 | 久久久久亚洲av无码专区| 久久99精品久久久久久不卡| 麻豆亚洲AV永久无码精品久久| 久久精品无码一区二区三区日韩| 麻豆成人久久精品二区三区免费 | 91久久婷婷国产综合精品青草| 久久性精品| 精品视频久久久久| 91麻精品国产91久久久久| 久久99国内精品自在现线| 狠狠精品久久久无码中文字幕| 久久人人爽人爽人人爽av| 国产精品成人久久久久三级午夜电影| 午夜精品久久久久久久| 久久久久久久久久免免费精品| 色综合合久久天天综合绕视看| 国产午夜久久影院| 久久精品一区二区国产| 国内精品久久人妻互换| 久久久久99精品成人片直播| 亚洲中文字幕无码久久2017 | 久久精品国产亚洲AV忘忧草18| 久久强奷乱码老熟女网站| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久毛片免费看一区二区三区|