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

            QuXiao

            每天進(jìn)步一點(diǎn)點(diǎn)!

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              50 隨筆 :: 0 文章 :: 27 評(píng)論 :: 0 Trackbacks

            #

            題目來源:

            PKU 1018 Communication System

             

            算法分類:

            枚舉+貪心

             

            原文:

            Communication System

            Time Limit:1000MS  Memory Limit:10000K

            Description

            We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
            By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

            Input

            The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

            Output

            Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

            Sample Input

            1 3

            3 100 25 150 35 80 25

            2 120 80 155 40

            2 100 100 120 110

             

            Sample Output

            0.649

             

            Source

            Tehran 2002, First Iran Nationwide Internet Programming Contest

             

             

            中文描述:

            你需要購買n種設(shè)備來組一個(gè)通信系統(tǒng),每一種設(shè)備,又是由一些不同的制造商生產(chǎn)的,不同制造商生產(chǎn)的同種設(shè)備會(huì)有不同的帶寬和價(jià)格。現(xiàn)在你要在每一個(gè)設(shè)備的制造商中選一個(gè),使得購買的n種設(shè)備,它們帶寬的最小值與價(jià)格之和的比最大。

             

            題目分析:

            一開始想到的就是暴搜,但是搜索的深度達(dá)到100,時(shí)間肯定是不允許的。想要解決這題,必須找到一個(gè)好的查找策略。再想想看這題的特點(diǎn),最后的答案,帶寬是選取所有設(shè)備中的最小值,而價(jià)格是選取所有設(shè)備的價(jià)格總和。如果某個(gè)制造商生產(chǎn)的某種設(shè)備,它的帶寬較高而價(jià)格較低,那么選取它的可能性就比較大。再進(jìn)一步說,如果所選取的n種設(shè)備的帶寬的最小值b已經(jīng)確定,那么對(duì)于某種設(shè)備,我們就可以在那些生產(chǎn)這種設(shè)備的,帶寬大于等于b的制造商中進(jìn)行選擇。當(dāng)然是選那個(gè)價(jià)格最低的設(shè)備,因?yàn)榇鸢傅姆肿右呀?jīng)確定為b,所以分母越小越好。看來只要枚舉b,再對(duì)于每個(gè)設(shè)備貪心的選擇最小價(jià)格就可以了,時(shí)間復(fù)雜度為OmnB),B為帶寬枚舉的數(shù)量。但問題又來了,應(yīng)該怎么枚舉帶寬,題目中并未給出帶寬的取值范圍,如果從0..maxB一個(gè)一個(gè)枚舉的話,既費(fèi)時(shí)又會(huì)造成過多重復(fù)情況(如果枚舉那些在輸入中出現(xiàn)的兩個(gè)連續(xù)帶寬之間的值,最后的答案是一樣的)。所以我們應(yīng)該采取某個(gè)方法記錄輸入中出現(xiàn)過的帶寬(STL中的set是個(gè)不錯(cuò)的選擇),再枚舉這些帶寬。在枚舉中,可能出現(xiàn)這種情況:枚舉b,選擇了n種設(shè)備,但選擇的所有設(shè)備的帶寬都大于b,那么最終用b/price就不是這種情況的正確答案。其實(shí)不用擔(dān)心,因?yàn)檎_答案一定大于b/price。假設(shè)上面這種情況的實(shí)際帶寬最小值是b’,那個(gè)當(dāng)我們?cè)偃ッ杜eb’時(shí),至少有一個(gè)設(shè)備的帶寬等于b’,這次得到的答案也就是上面那種情況的答案,所以最終還是能得到正確解。

             

            代碼:

            #include <iostream>

            #include <map>

            #include <set>

            #include <climits>

            using namespace std;

             

            const int MAX = 105;

             

            struct Info

            {

                            int band, price;

            };

             

            struct Device

            {

                            int manuNum;

                            Info info[MAX];

                            map<int, int> minPrice;                 //map[i] = j 表示帶寬>=i的最小價(jià)格是j

                            int minBand, maxBand;

            };

             

            Device device[MAX];

            int deviceNum;

            set<int> band;                                                                  //輸入中出現(xiàn)過的band

            set<int>::iterator start, end;

            int maxBand, minBand;                                 //需要枚舉的band的最值

             

            int cmp( const void *a , const void *b )

            {

                            Info *c = (Info *)a;

                            Info *d = (Info *)b;

                            if(c->band != d->band)

                                            return d->band - c->band;

                            else

                                            return c->price - d->price;

            }

             

            void Input ()

            {

                            int i, j, max, min;

                            band.clear();

                            cin>>deviceNum;

                            for (i=0; i<deviceNum; i++)

                            {

                                            device[i].minBand = INT_MAX;

                                            device[i].maxBand = -1;

                                            cin>>device[i].manuNum;

                                            for (j=0; j<device[i].manuNum; j++)

                                            {

                                                            cin>>device[i].info[j].band>>device[i].info[j].price;

                                                            band.insert(device[i].info[j].band);

                                                            if ( device[i].info[j].band > device[i].maxBand )

                                                                            device[i].maxBand = device[i].info[j].band;

                                                            if ( device[i].info[j].band < device[i].minBand )

                                                                            device[i].minBand = device[i].info[j].band;

                                            }

                                                                           

                            }

            }

             

            void Pre ()                                           //預(yù)處理

            {

                            int i, j, min, b;

                            //計(jì)算所需枚舉的帶寬的最值

                            maxBand = INT_MAX;                   //maxBand為所有設(shè)備帶寬最大值的最小值

                            minBand = INT_MAX;                    //minBand為所有設(shè)備帶寬最小值的最小值

                            for (i=0; i<deviceNum; i++)

                            {

                                            if ( device[i].maxBand < maxBand )

                                                            maxBand = device[i].maxBand;

                                            if ( device[i].minBand < minBand )

                                                            minBand = device[i].minBand;

                            }

             

                            //對(duì)于每個(gè)設(shè)備,找到帶寬大于等于某一值的最小價(jià)格

                            for (i=0; i<deviceNum; i++)

                            {

                                            //band從大到小,band相等時(shí)price從小到大

                                            qsort(device[i].info, device[i].manuNum, sizeof(Info), cmp);

                                            device[i].minPrice.clear();

                                            min = device[i].info[0].price;

                                            b = device[i].info[0].band;

                                            device[i].minPrice[b] = min;

                                            for (j=1; j<device[i].manuNum; j++)

                                            {

                                                            if ( device[i].info[j].band == b )

                                                                            continue;

                                                            if ( device[i].info[j].price < min )

                                                            {

                                                                            min = device[i].info[j].price;

                                                            }

                                                            b = device[i].info[j].band;

                                                            device[i].minPrice[b] = min;

                                            }

                            }             

            }

             

            void Solve ()

            {

                            Pre();

             

                            int b, i, totalPrice;

                            double rate, ans;

                            map<int, int>::iterator it;

                            ans = 0;

                            start = band.find(minBand);

                            end = band.find(maxBand);

                            end ++;

                            while ( start != end )

                            {

                                            b = *start;

                                            start ++;

                                            totalPrice = 0;

                                            for (i=0; i<deviceNum; i++)

                                            {

                                                            //找到帶寬大于等于b的最小價(jià)格

                                                            for (it=device[i].minPrice.begin(); it!=device[i].minPrice.end(); it++)

                                                            {

                                                                            if ( it->first >= b )

                                                                            {

                                                                                            totalPrice += it->second;

                                                                                            break;

                                                                            }

                                                            }

             

                                            }

                                            rate = double(b) / totalPrice;

                                            if ( rate > ans )

                                                            ans = rate;

                            }

             

                            printf("%.3f\n", ans);

            }

             

            int main ()

            {

                            int test;

                            cin>>test;

                            while ( test -- )

                            {

                                            Input ();

                                            Solve ();

                            }

             

                            return 0;

            }

            posted @ 2008-04-25 21:25 quxiao 閱讀(1528) | 評(píng)論 (6)編輯 收藏

                 摘要: 解題報(bào)告   題目來源: PKU 3513 Let's Go to the Movies   分類: 樹形DP   原文: Let's Go to the Movies   Time Limit: 1000MS ...  閱讀全文
            posted @ 2008-03-25 23:16 quxiao 閱讀(567) | 評(píng)論 (0)編輯 收藏

            解題報(bào)告

             

            題目來源:

            PKU 1505 Copying Books

             

            算法分類:

            DP

             

            原文:

            Copying Books

            Time Limit: 3000MS


            Memory Limit: 10000K

            Total Submissions: 1806


            Accepted: 404

            Description

            Before the invention of book-printing, it was very hard to make a copy of a book. All the contents had to be re-written by hand by so called scribers. The scriber had been given a book and after several months he finished its copy. One of the most famous scribers lived in the 15th century and his name was Xaverius Endricus Remius Ontius Xendrianus (Xerox). Anyway, the work was very annoying and boring. And the only way to speed it up was to hire more scribers.

            Once upon a time, there was a theater ensemble that wanted to play famous Antique Tragedies. The scripts of these plays were divided into many books and actors needed more copies of them, of course. So they hired many scribers to make copies of these books. Imagine you have m books (numbered 1, 2 ... m) that may have different number of pages (p1, p2 ... pm) and you want to make one copy of each of them. Your task is to divide these books among k scribes, k <= m. Each book can be assigned to a single scriber only, and every scriber must get a continuous sequence of books. That means, there exists an increasing succession of numbers 0 = b0 < b1 < b2, ... < bk-1 <= bk = m such that i-th scriber gets a sequence of books with numbers between bi-1+1 and bi. The time needed to make a copy of all the books is determined by the scriber who was assigned the most work. Therefore, our goal is to minimize the maximum number of pages assigned to a single scriber. Your task is to find the optimal assignment.

            Input

            The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 <= k <= m <= 500. At the second line, there are integers p1, p2, ... pm separated by spaces. All these values are positive and less than 10000000.

            Output

            For each case, print exactly one line. The line must contain the input succession p1, p2, ... pm divided into exactly k parts such that the maximum sum of a single part should be as small as possible. Use the slash character ('/') to separate the parts. There must be exactly one space character between any two successive numbers and between the number and the slash.

            If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book.

            Sample Input

            2

            9 3

            100 200 300 400 500 600 700 800 900

            5 4

            100 100 100 100 100

            Sample Output

            100 200 300 400 500 / 600 700 / 800 900

            100 / 100 / 100 / 100 100

            Source

            Central Europe 1998

             

             

            中文描述:

            題目大意是給你m1…m)本書,每本書有Pm頁,用kk<=m)個(gè)員工來復(fù)印這些書。每本書只能分配給一個(gè)員工來復(fù)印,并且每個(gè)員工必須復(fù)印一段連續(xù)的書籍,每個(gè)員工復(fù)印的時(shí)間取決于所復(fù)印書籍的總頁數(shù)。讓你給出相應(yīng)的分配,使得分配給員工的書籍頁數(shù)的最大值盡量小。注意,如果有多種分配的方案,使得第一個(gè)員工的書籍頁數(shù)盡量少,其次是第二個(gè)、第三個(gè)……以此類推。

             

            題目分析:

            我們可以從后往前推,最后一個(gè)員工,也就是第k個(gè)員工,他至少要復(fù)印第m本書,至多可以復(fù)印第k本到第m本(因?yàn)橹辽僖峙浣o前k-1個(gè)員工每人一本書)。假設(shè),第k名員工復(fù)制第ik<=i<=m)本書到第m本書,那么,所有員工復(fù)印書籍的最小時(shí)間就為第k名員工所需的時(shí)間以及前k-1名員工復(fù)制前i-1本書所需最小時(shí)間的較大的那個(gè)時(shí)間。這樣,問題的規(guī)模就從k個(gè)員工復(fù)印m本書減小到了k-1個(gè)員工復(fù)印i-1本書,而且求解過程中會(huì)不斷遇到前a個(gè)員工復(fù)印前b本書的最小時(shí)間。為了減小問題的規(guī)模以及記錄重復(fù)子問題的解,就可以用DP

            但僅僅算出最小時(shí)間的不夠的,還要給出分配的方案,這個(gè)稍微有點(diǎn)繁瑣。因?yàn)轭}目中說,如果有多種最優(yōu)的分配方案,應(yīng)該讓前面的員工分配的頁數(shù)盡量少。那么,可以從后推,在當(dāng)前的員工所復(fù)印的書籍頁數(shù)沒有超過最大頁數(shù)的情況下,讓其復(fù)印的頁數(shù)最大化。如果超過了最大頁數(shù),就把這本書分配給前一名員工。最后再按順序?qū)⒎峙浣Y(jié)果輸出出來。

             

            代碼:

            #include <cstdio>

            #include <climits>

            #include <cstring>

             

            const int MAX = 505;

            int book[MAX];

            __int64 total[MAX];                        //1~n本書的頁數(shù)

            int k, m;

            __int64 f[MAX][MAX];                  //f[i][j] = k 表示前i個(gè)人復(fù)制前j本書所需最少時(shí)間是k

            __int64 max;

            void Input ()

            {

                            scanf("%d%d", &m, &k);

                            int i;

                            for (i=1; i<=m; i++)

                                            scanf("%d", &book[i]);

            }

             

            __int64 Sum (int s, int e)                                               //s本書到第e本書的總頁數(shù)

            {

                            return (total[e] - total[s-1]);

            }

             

            __int64 Max (__int64 a, __int64 b)

            {

                            return ( a>b?a:b );

            }

             

            __int64 Min (int x, int y)                                //x個(gè)人復(fù)制前y本書所需的最少時(shí)間        x<=y

            {

            //考慮特殊情況

                            if ( f[x][y] != -1 )

                                            return f[x][y];

                            if ( y == 0 )

                                            return ( f[x][y] = 0 );

                            if ( x == 0 )

                                            return ( f[x][y] = INT_MAX );

             

                            int i;

                            __int64 temp;

                            f[x][y] = INT_MAX;

                            for (i=x-1; i<y; i++)

                            {

            //x個(gè)人復(fù)制第i+1到第y本書與前x-1個(gè)人復(fù)制前i本書的時(shí)間較大的時(shí)間

                                            temp = Max( Min(x-1, i), Sum(i+1, y) );                 

                                            if ( temp < f[x][y] )

                                            {

                                                            f[x][y] = temp;

                                            }

                            }

                            return f[x][y];

            }

             

            void Output ()

            {

                            int i, p;

                            __int64 temp;

                            int slash[MAX];

                            max = f[k][m];

                            memset(slash, 0, sizeof(slash));

                            temp = 0;

                            p = k;

                            for (i=m; i>0; i--)

                            {

                                            //讓后面的員工盡量復(fù)印最多的書籍

                                            if ( temp + book[i] > max || i < p )

                                            {

                                                            slash[i] = 1;

                                                            temp = book[i];

                                                            p --;

                                            }

                                            else

                                            {

                                                            temp += book[i];

                                            }

                            }

             

                            for (i=1; i<=m; i++)

                            {

                                            printf("%d", book[i]);

                                            if ( slash[i] == 1 )

                                                            printf(" / ");

                                            else if ( i != m )

                                                            printf(" ");

                            }

                            printf("\n");

            }

             

            void Solve ()

            {

                            int i, j;

                            //預(yù)處理書籍頁數(shù)的和

                            total[0] = 0;

                            for (i=1; i<=m; i++)

                                            total[i] = total[i-1] + book[i];

             

                            memset(f, -1, sizeof(f));

                           

                            Min(k, m);

                           

                            Output();

            }

             

            int main ()

            {

                            int test;

                            scanf("%d", &test);

                            while ( test-- )

                            {

                                            Input ();

                                            Solve ();

                            }

             

                            return 0;

            }

             

             

            程序分析與心得:

            時(shí)間復(fù)雜度O(n2),空間復(fù)雜度O(n2)

            在用記憶化搜索解決DP問題時(shí),往往比較符合人的思維,容易想到模型,編程比較簡(jiǎn)單。在解題過程中,除了可以按照常理順著推,也可以嘗試逆向思維,從最后的狀態(tài)倒著推,這樣可以使問題想得更加透徹,有比較好的效果。

            posted @ 2008-03-10 15:11 quxiao 閱讀(560) | 評(píng)論 (0)編輯 收藏

            題目大意:
                給你n個(gè)藥的序列,牛從時(shí)間1開始吃藥,在奇數(shù)時(shí)間吃藥可以增加彈跳力,在偶數(shù)時(shí)間吃藥則會(huì)減少彈跳力。在某一時(shí)間,你可以跳過一些藥,但一旦吃過某種藥,你就不能在選前面的藥了。問你某一個(gè)吃藥的序列,使牛最終的彈跳力最大。

            思路:
                雖然題目不難,但思考題目的過程十分有意思。對(duì)于某種藥,共有4中狀態(tài):在奇數(shù)時(shí)間吃、在奇數(shù)時(shí)間不吃、在偶數(shù)時(shí)間吃以及在偶數(shù)時(shí)間不吃。關(guān)鍵在于這4種狀態(tài)之間的轉(zhuǎn)移。因?yàn)槿绻^某種藥是不需要花費(fèi)時(shí)間的,所以在某2次的吃藥時(shí)間內(nèi),時(shí)間相當(dāng)于是靜止的,一直維持在第1次吃藥的時(shí)間段內(nèi)。
                所以可用一數(shù)組max[i][2][2]表示狀態(tài),第i種藥在奇/偶時(shí)間段內(nèi)吃/不吃。可得狀態(tài)轉(zhuǎn)移可表示為:
                max[i][0][0] = Max (max[i-1][0][0], max[i-1][0][1]);
                max[i][0][1] = Max (max[i-1][1][0], max[i-1][1][1]) - high[i];
                max[i][1][0] = Max (max[i-1][1][0], max[i-1][1][1]);
                max[i][1][1] = Max (max[i-1][0][0], max[i-1][0][1]) + high[i];

            代碼:

            #include <iostream>
            using namespace std;

            const int MAX = 150005;
            int high[MAX];
            int max[MAX][2][2];
            int n;

            void Input ()
            {
                scanf("%d", &n);
                int i;
                for (i=1; i<=n; i++)
                    scanf("%d", &high[i]);

            }

            int Max (int a, int b)
            {
                return ( a>b?a:b );
            }

            void Solve ()
            {
                int i;
                for (i=1; i<=n; i++)
                {
                    max[i][0][0] = Max (max[i-1][0][0], max[i-1][0][1]);
                    max[i][0][1] = Max (max[i-1][1][0], max[i-1][1][1]) - high[i];
                    max[i][1][0] = Max (max[i-1][1][0], max[i-1][1][1]);
                    max[i][1][1] = Max (max[i-1][0][0], max[i-1][0][1]) + high[i];
                }
                printf("%d\n", Max ( Max(max[n][0][0], max[n][0][1]), Max(max[n][1][0], max[n][1][1])) );
            }

            int main ()
            {
                Input ();
                Solve ();

                return 0;
            }
            posted @ 2008-02-02 21:41 quxiao 閱讀(942) | 評(píng)論 (0)編輯 收藏

            題目大意:
                給定n個(gè)連續(xù)的長度為1的矩形的高度h(1<=n<=100000,0<=hi<=1000000000),問你其中能構(gòu)成的最大矩形的面積是多少。

            思路:
                很顯然,用DP。但關(guān)鍵是怎樣表示狀態(tài),一開始想用一個(gè)二維數(shù)組min[][]表示從i~j的最小高度,面積就等于min[i][j]*(j-i+1)。但很不幸,根據(jù)題目給定的n的范圍,這個(gè)二維數(shù)組根本無法創(chuàng)建。:(
                后來從論壇上得到提示,因?yàn)閷?duì)于圖中的某個(gè)面積最大的矩形,必然有一個(gè)最低的高度h[k],即矩形的高等于h[k],以第k塊矩形的高度,最左邊可以到達(dá)這個(gè)矩形的左邊,最右邊可以到達(dá)這個(gè)矩形的右邊。所以,可以以每塊矩形進(jìn)行擴(kuò)展,求出最左邊和最右邊(即兩邊的高度都大于等于這塊的高度),得出面積s[i],這樣就可求出最大的s[i]了。

            代碼:

            #include <cstdio>

            const int MAX = 100005;
            __int64 h[MAX];
            __int64 left[MAX], right[MAX];        //left[i] = j表示第i個(gè)矩形以它的高度到達(dá)最左邊的下標(biāo)
            int n;

            bool Input ()
            {
                scanf("%d", &n);
                if ( n == 0 )
                    return false;
                int i;
                for (i=1; i<=n; i++)
                    scanf("%I64d", &h[i]);
                h[0] = h[n+1] = -1;
                return true;
            }

            void Solve ()
            {
                int i;
                __int64 temp, max;
                for (i=1; i<=n; i++)
                {
                    left[i] = right[i] = i;
                }

                for (i=1; i<=n; i++)
                {
                    while ( h[left[i]-1] >= h[i] )
                        left[i] = left[left[i]-1];
                }
                for (i=n; i>0; i--)
                {
                    while ( h[right[i]+1] >= h[i] )
                        right[i] = right[right[i]+1];
                }

                max = 0;
                for (i=1; i<=n; i++)
                {
                    temp = h[i] * (right[i] - left[i] + 1);
                    if ( temp > max )
                        max = temp;
                }

                printf("%I64d\n", max);
            }

            int main ()
            {
                while ( Input() )
                {
                    Solve();
                }

                return 0;
            }


            posted @ 2008-02-01 19:34 quxiao 閱讀(1842) | 評(píng)論 (0)編輯 收藏

            題目大意:

                給定一個(gè)時(shí)間期間n,電腦的價(jià)格c,以及電腦的維修費(fèi)用m(y,z)(第y臺(tái)電腦從y年用到第z年總的維修費(fèi)用)。讓你求出在期限n中使用電腦的最低費(fèi)用。

            思路:
                為了讓總費(fèi)用最低,你必須作出這樣的決策:假設(shè)你正在使用某一臺(tái)電腦已用到y(tǒng)年,你y+1年是繼續(xù)用這臺(tái)電腦,還是重新買第y+1臺(tái)電腦(注意,這里的y+1是指輸入中的第y+1行電腦,而不是指你已購買了y+1臺(tái)電腦,因?yàn)閥年只能買輸入中的第y行電腦,為了不產(chǎn)生混淆,將電腦用編號(hào)表示)。顯然,某一階段的最優(yōu)解并不能一定導(dǎo)致全局的最優(yōu)解,所以肯定不能用貪心。
                我們從最后的情況來考慮,最后必然是某一個(gè)編號(hào)為y的電腦,從第y年使用到第n年,而前面的1~y-1年,自己只可能購買編號(hào)為1~y-1的電腦使用到y(tǒng)-1年。這樣,問題的范圍就減小了,從編號(hào)為1~n的電腦使用n年,降低到了編號(hào)為1~y-1的電腦使用y-1年。經(jīng)分析,可推出遞推式:
                F[n] = min { F[i] + c + m[i+1][n] | 0<=i<=n-1 }
            F[n]表示n臺(tái)電腦使用n年的最低費(fèi)用

            代碼:

            #include <cstdio>
            #include <climits>
            #include <cstring>

            const int MAX = 1005;
            int n, c;
            int mend[MAX][MAX];
            int f[MAX];
            int cost;

            bool Input ()
            {
                if ( scanf("%d", &c) == EOF )
                    return false;
                scanf("%d", &n);
                int i, j;
                for (i=1; i<=n; i++)
                {
                    for (j=i; j<=n; j++)
                        scanf("%d", &mend[i][j]);
                }
                return true;
            }


            void Solve ()
            {
                int i, j;
                memset(f, 0, sizeof(f));
                for (i=1; i<=n; i++)
                {
                    f[i] = INT_MAX;
                    for (j=0; j<i; j++)
                    {
                        if ( f[j] + mend[j+1][i] + c < f[i] )
                            f[i] = f[j] + mend[j+1][i] + c;
                    }
                }
                printf("%d\n", f[n]);
            }

            int main ()
            {
                while ( Input() )
                {
                    Solve ();
                }

                return 0;
            }
            posted @ 2008-01-28 14:45 quxiao 閱讀(475) | 評(píng)論 (0)編輯 收藏

            題意:
                就是有這樣一個(gè)序列:1 12 123 1234 12345 .....,輸入序列的下標(biāo),讓你算出該序列所在下標(biāo)的字符

            思路:
                一開始想用字符串模擬來做,結(jié)果TLE。后來看了discuss,又想了一下,發(fā)現(xiàn)可以按規(guī)律將序列分成幾段,然后再在每段中查找。具體做法是:先按序列 中數(shù)字的位數(shù)來分,112123...123456789是一段,1..10 1..11 1..12 ... 1..99是一段,1..100 ... 1..999是一段,以此類推。確定了是在上面的哪一段以后,再按類似的思想確定這個(gè)下標(biāo)是在哪個(gè)12345...n的序列,最后判斷是在其中哪個(gè)數(shù)字的 哪一位。

            代碼:
            #include <iostream>
            #include <cmath>
            using namespace std;

            const long long a[] = {0, 45, 9045, 1395495, 189414495, 2147483648};            //112123...9, 11231234...99, ... 的位數(shù)
            const long long b[] = {1, 11, 192, 2893, 38894, 488895, 5888896};                //1, 1234...10, 1234...100, ...的位數(shù)

            int digit (int n)
            {
                int ans = 1;
                while ( n / 10 != 0 )
                {
                      n /= 10;
                      ans ++;
                }
                return ans;
            }

            char Pos (int n, long long index)      //在1234...n中找到下標(biāo)為index的字符
            {
                 long long i, j;
                 long long pos = 0;
                 for (i=1; i<=n; i++)
                 {
                     pos += digit(i);
                     if ( pos >= index )
                        break;
                 }
                
                 pos -= digit(i);               //定位在i上
                 j = digit(i) - (index - pos);
                 //if ( j == digit(i) - 1 )
                 //   cout<<endl;
                 while ( j > 0 )
                 {
                       i /= 10;
                       j --;
                 }

                 return (i % 10) + '0';
            }


            char Find (long long pos)
            {
                 long long p, t;
                 int index = 0;
                 int temp;
                 while ( a[index] < pos )
                 {
                       index ++;
                 }
                 p = a[index - 1];
                
                 p += b[index - 1];
                 temp = int(pow(10.0, index-1));
                 t = b[index - 1] + index;
                 while ( p < pos )
                 {
                       p += t;
                       t += index;
                       temp ++;
                 }
                
                 p -= t - index;
                
                 return Pos(temp, pos-p);
            }

            int main ()
            {
                int test;
                long long i;
                cin>>test
                while ( test-- )
                {
                      cin>>i;
                      cout<<Find(i)<<endl;
                }

                return 0;
            posted @ 2008-01-19 16:46 quxiao 閱讀(1708) | 評(píng)論 (0)編輯 收藏

                一開始看還以為是一道博弈的題目,再仔細(xì)看才發(fā)現(xiàn)并不是博弈,也不是很難。大致意思是:有n堆石子,第i堆有Ki個(gè)石子,每輪一方可以從任意堆中取出一個(gè)或多個(gè)石子,所有石子都被取光時(shí),游戲也結(jié)束了,那個(gè)最后一輪拿走石子的人就是勝利者。問你有多少種方法使對(duì)方處于必?cái)〉木置妗n}目并不難,是因?yàn)轭}目中已經(jīng)告訴你了產(chǎn)生必?cái)【置娴臈l件:如果所有堆的石子數(shù)的異或和為0,那么處于此局面的人就必?cái) ?br>    因?yàn)槊看沃荒軓囊粋€(gè)堆中取石子,所以只要對(duì)于每個(gè)堆i,先求出其他所有堆的異或和temp,再看0~Ki-1與這個(gè)異或和再進(jìn)行異或是否為0,只要為0就得到一種勝利的方法。自己先是想枚舉0~Ki-1,與temp進(jìn)行異或。后來感覺沒有必要,只要Ki>temp就可以了,因?yàn)槿魪亩裪中取出x個(gè)石子,Ki-x異或temp==0 <==> Ki-x==temp,只要Ki>temp,就存在Ki-x==temp。

            #include <cstdio>

            #define PILE 1001

            __int64 stone[PILE], test;       //test為所有石子數(shù)的異或和
            int piles;

            bool Input ()
            {
                scanf("%d", &piles);
                if ( piles == 0 )
                    return false;
               
                int i;
                for (i=0; i<piles; i++)
                    scanf("%I64d", &stone[i]);
                return true;
            }

            void Solve ()
            {
                int i, ans;
                __int64 temp;
                test = 0;
                ans = 0;
                for (i=0; i<piles; i++)
                    test ^= stone[i];
               
                if ( test != 0 )
                {
                    for (i=0; i<piles; i++)
                    {
                        temp = test ^ stone[i];      //再與stone[i]做一次異或,相當(dāng)于除stone[i]對(duì)其他所有堆的石子進(jìn)行異或

                        if ( stone[i] > temp )
                            ans++;
                    }
                }
                printf("%d\n", ans);
            }

            int main ()
            {
                while ( Input() )
                {
                    Solve();
                }
               
                return 0;
            }


            posted @ 2007-12-07 21:41 quxiao 閱讀(719) | 評(píng)論 (4)編輯 收藏

                地圖上有一些beeper,讓你從起點(diǎn)搜集所有beeper,再回到起點(diǎn)。但你只可以水平或者豎直的走,不能走對(duì)角線。讓你找出這樣走的最短路徑長度。
                因?yàn)榈貓D最大只有20×20,而beeper最多也只有10個(gè),所以可以考慮用深搜,找到所有可能路徑,在其中加一些簡(jiǎn)單的減枝就可以了。起初以為會(huì)超時(shí),可最后還是0ms。:)

            Source Code

            Problem: 2907
            User: QuXiao
            Memory: 176K
            Time: 0MS
            Language: C++
            Result: Accepted
            • Source Code
            • #include <iostream>
              #include <climits>
              using namespace std;

              struct Point
              {
              int x, y;
              };

              int num, X, Y;
              Point start, beeper[15];
              int shortest;
              int visited[15];


              int Length (Point p1, Point p2)
              {
              return abs(p1.x - p2.x) + abs(p1.y - p2.y);
              }

              void Input ()
              {
              int i;
              cin>>X>>Y;
              cin>>start.x>>start.y;
              cin>>num;
              for (i=0; i<num; i++)
              cin>>beeper[i].x>>beeper[i].y;
              }

              void DFS (int cur, int len, int n)
              {
              if ( n == num )
              {
              int t = Length(beeper[cur], start);
              if ( len + t < shortest )
              shortest = len + t;
              }
              else if ( len < shortest )
              {
              int i;
              for (i=0; i<num; i++)
              {
              if ( visited[i] == 0 )
              {
              visited[i] = 1;
              DFS (i, len+Length(beeper[cur], beeper[i]), n+1);
              visited[i] = 0;
              }
              }
              }
              }


              void Solve ()
              {
              int i, t;
              shortest = INT_MAX;
              memset(visited, 0, sizeof(visited));
              for (i=0; i<num; i++)
              {
              t = Length(beeper[i], start);
              visited[i] = 1;
              DFS (i, t, 1);
              visited[i] = 0;
              }
              cout<<"The shortest path has length "<<shortest<<endl;
              }

              int main ()
              {
              int test;
              cin>>test;
              while ( test-- )
              {
              Input ();
              Solve ();
              }

              return 0;
              }



            posted @ 2007-12-07 19:31 quxiao 閱讀(375) | 評(píng)論 (1)編輯 收藏

                大家好,我對(duì)算法比較感興趣。希望能借此平臺(tái),與我有同樣愛好的朋友們能夠多多交流,共同進(jìn)步!
            posted @ 2007-12-07 19:11 quxiao 閱讀(66) | 評(píng)論 (0)編輯 收藏

            僅列出標(biāo)題
            共5頁: 1 2 3 4 5 
            久久伊人五月丁香狠狠色| 99久久国产综合精品女同图片| 色噜噜狠狠先锋影音久久| 久久精品夜色噜噜亚洲A∨| 久久久国产视频| 天天综合久久久网| 成人综合久久精品色婷婷| 国产成人久久精品一区二区三区| AAA级久久久精品无码区| 久久人人爽人人爽人人爽 | 热久久国产欧美一区二区精品| 亚洲va久久久久| 久久最近最新中文字幕大全| 久久午夜福利电影| 青青青青久久精品国产| 亚洲va中文字幕无码久久不卡| 国产精品成人99久久久久 | 国内精品人妻无码久久久影院| 久久精品国产亚洲5555| 久久久久久九九99精品| 中文字幕无码久久精品青草 | 日韩十八禁一区二区久久| 91精品国产高清久久久久久io | 久久国产精品二国产精品| 精品久久久久久亚洲精品| 久久福利资源国产精品999| 久久激情五月丁香伊人| 久久精品人人做人人爽电影| 久久99精品久久久久久hb无码| 伊人 久久 精品| 欧洲国产伦久久久久久久| 久久精品国产99国产精品澳门| 婷婷久久香蕉五月综合加勒比| 亚洲精品美女久久久久99小说| 国产日韩久久久精品影院首页| 狼狼综合久久久久综合网| 久久婷婷国产剧情内射白浆| 欧美黑人激情性久久| 国产成人精品久久| 久久香蕉超碰97国产精品| 奇米综合四色77777久久|