• <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;
            }
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿(1)

            隨筆檔案

            文章檔案

            搜索

            最新評論

            久久久久高潮毛片免费全部播放| 久久这里只有精品久久| 狠狠久久综合伊人不卡| 国产精品久久波多野结衣| 久久99国产精品久久久 | 久久无码中文字幕东京热| 国产激情久久久久影院老熟女| 99精品国产在热久久无毒不卡| 久久亚洲美女精品国产精品| 久久亚洲精品成人av无码网站| aaa级精品久久久国产片| 99久久精品国产毛片| 久久99精品国产麻豆不卡| 久久精品国产亚洲欧美| 国产女人aaa级久久久级| 亚洲精品无码久久久久去q| 91久久精品91久久性色| 狠狠综合久久综合88亚洲| 国产亚洲美女精品久久久| 久久亚洲私人国产精品| 亚洲国产成人久久精品99 | 久久精品国产亚洲av麻豆图片| 精品久久久久久久| 波多野结衣久久一区二区 | 久久精品视屏| 夜夜亚洲天天久久| 国产午夜福利精品久久| 久久精品www| 国产成人99久久亚洲综合精品| 久久久久AV综合网成人| 久久久精品2019免费观看| 亚洲午夜久久久影院| 99久久免费国产特黄| 色综合久久最新中文字幕| 免费观看久久精彩视频| 日本精品久久久久中文字幕| 大蕉久久伊人中文字幕| 国产精品免费看久久久香蕉| 久久久精品久久久久特色影视| 亚洲综合久久夜AV | 久久精品国产只有精品2020|