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

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            九九久久自然熟的香蕉图片| 久久99免费视频| 久久久久九国产精品| 99久久做夜夜爱天天做精品| 久久久一本精品99久久精品88| 99精品久久精品一区二区| 久久久久无码精品国产| 天天综合久久久网| 久久人人爽人人爽人人片AV东京热| 午夜天堂精品久久久久| 麻豆精品久久精品色综合| 久久婷婷五月综合成人D啪| 老色鬼久久亚洲AV综合| 国产精品免费久久久久影院 | 久久久久久久久久久精品尤物 | 亚洲欧美日韩久久精品| 亚洲精品蜜桃久久久久久| 精品亚洲综合久久中文字幕| 日韩中文久久| 日本道色综合久久影院| 欧洲精品久久久av无码电影 | 久久se精品一区二区| 久久精品国产2020| 亚洲乱码日产精品a级毛片久久| 国产成年无码久久久久毛片| 中文字幕无码久久人妻| 国产精品成人无码久久久久久 | 精品久久久无码中文字幕天天| 看久久久久久a级毛片| 四虎国产精品成人免费久久| 久久久精品波多野结衣| 久久夜色tv网站| 91久久精品91久久性色| 国产成人精品免费久久久久| 久久这里只有精品18| 国产亚洲精品久久久久秋霞| 热久久最新网站获取| 99久久做夜夜爱天天做精品| 久久精品视频一| 久久久亚洲裙底偷窥综合| 99精品久久精品一区二区|