• <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>

            C++天空

            cpp_stu2's Land

            re: 對一些DP題目的小結 姜雨生 2007-06-30 22:59
            應該可以更加優化
            re: 對一些DP題目的小結 姜雨生 2007-06-30 22:55
            Margaritas on the River Walk
            Time Limit:1000MS Memory Limit:65536K
            Total Submit:309 Accepted:132

            Description


            One of the more popular activities in San Antonio is to enjoy margaritas in the park along the river know as the River Walk. Margaritas may be purchased at many establishments along the River Walk from fancy hotels to Joe’s Taco and Margarita stand. (The problem is not to find out how Joe got a liquor license. That involves Texas politics and thus is much too difficult for an ACM contest problem.) The prices of the margaritas vary depending on the amount and quality of the ingredients and the ambience of the establishment. You have allocated a certain amount of money to sampling different margaritas.

            Given the price of a single margarita (including applicable taxes and gratuities) at each of the various establishments and the amount allocated to sampling the margaritas, find out how many different maximal combinations, choosing at most one margarita from each establishment, you can purchase. A valid combination must have a total price no more than the allocated amount and the unused amount (allocated amount – total price) must be less than the price of any establishment that was not selected. (Otherwise you could add that establishment to the combination.)

            For example, suppose you have $25 to spend and the prices (whole dollar amounts) are:

            Vendor A B C D H J
            Price 8 9 8 7 16 5

            Then possible combinations (with their prices) are:

            ABC(25), ABD(24), ABJ(22), ACD(23), ACJ(21), ADJ( 20), AH(24), BCD(24), BCJ(22), BDJ(21), BH(25), CDJ(20), CH(24), DH(23) and HJ(21).

            Thus the total number of combinations is 15.


            Input


            The input begins with a line containing an integer value specifying the number of datasets that follow, N (1 ≤ N ≤ 1000). Each dataset starts with a line containing two integer values V and D representing the number of vendors (1 ≤ V ≤ 30) and the dollar amount to spend (1 ≤ D ≤ 1000) respectively. The two values will be separated by one or more spaces. The remainder of each dataset consists of one or more lines, each containing one or more integer values representing the cost of a margarita for each vendor. There will be a total of V cost values specified. The cost of a margarita is always at least one (1). Input values will be chosen so the result will fit in a 32 bit unsigned integer.


            Output


            For each problem instance, the output will be a single line containing the dataset number, followed by a single space and then the number of combinations for that problem instance.


            Sample Input


            2
            6 25
            8 9 8 7 16 5
            30 250
            1 2 3 4 5 6 7 8 9 10 11
            12 13 14 15 16 17 18 19 20
            21 22 23 24 25 26 27 28 29 30

            Sample Output


            1 15
            2 16509438

            Hint


            Note: Some solution methods for this problem may be exponential in the number of vendors. For these methods, the time limit may be exceeded on problem instances with a large number of vendors such as the second example below.


            Source
            Greater New York 2006
            急需 我也要樓主 幫我傳一份吧
            郵箱:cpp_student@163.com
            謝謝!!!
            re: 狀態壓縮DP, pku3020 姜雨生 2007-06-30 10:35
            真是太好了
            以后多向你請教
            算你狠
            我USACO全過了
            你還在做A+B!
            re: 凸包... 姜雨生 2007-06-30 10:26
            #include<fstream>
            #include<cstdlib>
            using namespace std;
            ifstream fin ("bag.in");
            ofstream fout ("bag.out");
            struct xys
            {
            int x;
            int y;
            };
            int N;//數目
            xys xy[101];//坐標系
            int top;//堆棧頂
            int stk[101];//堆棧
            void swap(xys *a,xys *b)
            {
            xys tmp = *a;
            *a = *b;
            *b =tmp;
            }
            int multi(xys a,xys b,xys c)
            {
            return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);//求叉積
            }
            bool comp(xys p1,xys p2)
            {
            int t;
            t=multi(p1,p2,xy[0]);
            if ((t>=0)&&((p1.x-xy[0].x)+(p1.y-xy[0].y)<(p2.x-xy[0].x)+(p2.y-xy[0].y)))
            return true;//叉積正確
            return false;
            }
            void sort(int p,int r)
            {
            int i,j;
            xys x;
            if (r-p+1<=5)
            {
            for (j=p+1;j<=r;j++)
            {
            i=j;
            while(i>1&&comp(xy[i],xy[i-1]))
            {
            swap(&xy[i],&xy[i-1]);//交換元素
            i--;
            }
            }
            }
            else
            {
            x=xy[p+rand()%(r-p+1)];//隨即選區一個支點
            i=p,j=r;
            do
            {
            while (comp(xy[i],x))i++;
            while (comp(x,xy[j]))j--;
            if (i<j)swap(&xy[i],&xy[j]);
            }//一次規劃
            while (i<j);
            sort(p,j);//前半部
            sort(p+1,r);//后半部
            }
            }
            void init()
            {
            int i;
            fin>>N;
            for(i=0;i<N;i++){
            fin>>xy[i].x>>xy[i].y;
            if (xy[i].y<=xy[0].y&&xy[i].x<xy[0].y) swap(xy[0],xy[i]);//交換
            }
            sort(1,N-1);
            }
            void graham()
            {
            int i;
            for(i=1;i<=3;i++) stk[i]=i-1;
            top=3;
            for(i=3;i<N;i++)
            {
            while(multi(xy[i],xy[stk[top]],xy[stk[top-1]])>=0) top--;//所有未向左傳的點去掉
            top++;
            stk[top]=i;//入棧
            }
            for (i=1;i<=top;i++)
            fout<<xy[stk[i]].x<<" "<<xy[stk[i]].y<<endl;
            }
            int main (void)
            {
            init();
            graham();//掃描出凸包,打印
            return 0;
            }
            <2007年6月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            1234567

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案

            文章檔案

            搜索

            最新評論

            久久久久久精品免费看SSS | 久久综合久久美利坚合众国| 四虎国产精品免费久久| 91精品免费久久久久久久久| 香港aa三级久久三级| 91久久精品视频| 久久久久亚洲av成人网人人软件| 99久久精品免费看国产一区二区三区| 伊人久久大香线焦综合四虎| 久久午夜福利电影| 51久久夜色精品国产| 久久中文精品无码中文字幕| 亚洲综合伊人久久综合| 国内精品久久久久久久亚洲| 91精品国产综合久久精品| 久久久亚洲欧洲日产国码是AV| 久久99精品久久久久久动态图| 99久久这里只精品国产免费| 国产精品99久久免费观看| 日日狠狠久久偷偷色综合0 | 久久国产免费直播| 亚洲综合久久综合激情久久| 亚洲中文久久精品无码ww16 | 亚洲欧美一级久久精品| 日韩精品国产自在久久现线拍| 欧美午夜精品久久久久免费视| 久久亚洲熟女cc98cm| 国产成人香蕉久久久久| 亚洲国产天堂久久久久久| 久久九九全国免费| 国产99精品久久| 国产精品久久久久久久| 久久午夜无码鲁丝片| 亚洲va久久久噜噜噜久久天堂| 午夜天堂精品久久久久| 欧美亚洲国产精品久久| 久久人人爽人人爽人人片AV东京热| 久久99精品久久久久久噜噜| 狠狠久久综合伊人不卡| 久久精品国产72国产精福利| 久久久久国产精品嫩草影院|