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

            GoogleCodejam2009 Round 1C Bribe the Prisoners

            Bribe the Prisoners

            Problem

            In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

            All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

            Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

            Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

            Input

            The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as

            P Q
            where P is the number of prison cells and Q is the number of prisoners to be released.
            This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.

             

            Output

            For each test case, output one line in the format

            Case #X: C
            where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.

             

            Limits

            1 ≤ N ≤ 100
            QP
            Each cell number is between 1 and P, inclusive.

            Small dataset

            1 ≤ P ≤ 100
            1 ≤ Q ≤ 5

            Large dataset

            1 ≤ P ≤ 10000
            1 ≤ Q ≤ 100

            Sample


            Input
             

            Output
             
            2
            8 1
            3
            20 3
            3 6 14
            Case #1: 7
            Case #2: 35

            Note

            In the second sample case, you first release the person in cell 14, then cell 6, then cell 3. The number of gold coins needed is 19 + 12 + 4 = 35. If you instead release the person in cell 6 first, the cost will be 19 + 4 + 13 = 36.


            題目分析:
            從直覺上來說,這是一道動態(tài)規(guī)劃的題目,關鍵是如何建立狀態(tài)遞推。有一個很明顯的規(guī)律是,釋放一個牢房的犯人,只能影響到左邊第一個空的牢房和右邊第一個空的牢房,而與其它的無關。所以,釋放了一個囚犯,整個連續(xù)的牢房被分成了2段,而這兩段又都可以看成是單獨的兩個互不影響的一段,這樣,腦子里有一種很直覺的想法就是,這是一棵類似于二叉樹的結構,這顆二叉樹最后的形態(tài)就決定了最終的結果。
            我們從第二個Case為例子介紹算法:
            1.首先對該題所提到的監(jiān)獄增加兩個cell,0號和P + 1號, 這兩個cell是不存在的,只是為了增加程序的可編寫和公式的一致,我們用一個vector v 來存儲釋放囚犯的監(jiān)獄號,v按照從小到達的順序排列,如第二個例子中,v(0...4) = (0,3, 6, 14, 21)
            2. 我們用F[i][j]表示 從v[i]到v[j]這一段中所需要的賄賂金最小值,那么,F(xiàn)[0][4]就是最后需要的結果, 代表從v[0]到v[4]也就是從(0, 21)這之間的牢房中釋放囚犯所需要的錢(不包括邊界,實際需要錢賄賂的囚犯在1到20號房子中)
            3. 例如第三個例子,F(xiàn)[0][4] = Min(F[0][i] + F[i][3]) + (v[4] - v[0] - 2) , 其可以中i = 1, 2, 3
                可以從第三個例子中看到,無論你選擇釋放哪一個囚犯,所需的金額都是一定的,正好是這段之間住人的牢房數(shù) - 1
            4.更加抽象出最終的公式, 我們用L代表左邊界, R代表右邊界
                F[L][R] = Min(F[L][i] + F[i][R]) + v[R] - V[L] - 2,   i = L + 1, L + 2, ……R- 1,  當L + 1 != R時
                F[L][R] = 0, 當L + 1 == R時, 這個就是上面提到的二叉樹的葉子節(jié)點
               通過這個公式就可以得到最終的結果了。

             1#include <iostream>
             2#include <vector>
             3#include <queue>
             4#include <string>
             5#include <algorithm>
             6#include <set>
             7#include <map>
             8using namespace std;
             9
            10#define ONLINEJUDGE
            11#define MAXN 11000
            12#define MAXQ 110
            13#define MAXP 110
            14#define MIN(a, b) ((a) < (b) ? (a):(b))
            15
            16int P, Q;
            17vector<int> v;
            18vector<int> Ret, buf;
            19int F[MAXP][MAXP];
            20
            21int Find(int l, int r)
            22{
            23    if(l + 1 == r)
            24    {
            25        F[l][r] = 0;
            26        return F[l][r];
            27    }

            28    if(F[l][r] >= 0return F[l][r];
            29
            30    int i, j;
            31    int iMin;
            32    iMin = 999999999;
            33    for(i = l + 1; i < r; i++)
            34    {
            35        iMin = MIN(iMin, Find(l, i) + Find(i, r));
            36    }

            37    F[l][r] = iMin + v[r] - v[l] - 2;
            38    return F[l][r];
            39}

            40
            41int main()
            42{
            43#ifdef ONLINEJUDGE
            44    freopen("C-large.in""r", stdin);
            45    freopen("C-large.out""w", stdout);
            46#endif
            47
            48    int iCaseTimes, i, j;
            49    int iBuf;
            50    int iMax, iRet, iMin;
            51
            52    scanf("%d"&iCaseTimes);
            53    for(int k = 0; k < iCaseTimes; k++)
            54    {
            55        printf("Case #%d: ", k + 1);
            56        scanf("%d%d"&P, &Q);
            57        v.clear();
            58        v.push_back(0);
            59        for(i = 0; i < Q; i++)
            60        {
            61            scanf("%d"&iBuf);
            62            v.push_back(iBuf);
            63        }

            64        v.push_back(P + 1);
            65
            66        iMin = 0;
            67        memset(F, -1sizeof(F));
            68        sort(v.begin(), v.end());
            69        
            70        iMin = 999999999;
            71        for(i = 1; i < v.size() - 1; i++)
            72        {
            73            iMin = MIN(iMin, Find(0, i) + Find(i, v.size() - 1));
            74        }

            75        F[0][v.size() - 1= iMin + v[v.size() - 1- v[0- 2;
            76        printf("%d\n", F[0][v.size() - 1]);
            77    }

            78    return 0;
            79}

            posted on 2009-09-14 19:28 Philip85517 閱讀(1435) 評論(2)  編輯 收藏 引用 所屬分類: GoogleCodeJam

            評論

            # re: GoogleCodejam2009 Round 1C Bribe the Prisoners[未登錄] 2009-09-15 16:09 vincent

            googlecodejam啊 ..貌似是9月2日?
            當天有事情沒參加..orz  回復  更多評論   

            # re: GoogleCodejam2009 Round 1C Bribe the Prisoners[未登錄] 2009-09-15 23:32 Philip85517

            @vincent
            9月2號開始的是資格賽,這個是上個星期天的比賽。
            估計Round2 是死活進不去了,太弱了……
              回復  更多評論   

            導航

            <2009年9月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            統(tǒng)計

            常用鏈接

            留言簿

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            免费观看久久精彩视频| 久久人人青草97香蕉| 青青青青久久精品国产| 久久99精品久久久久久秒播| 亚洲日韩欧美一区久久久久我| 精品人妻伦九区久久AAA片69| 热re99久久精品国产99热| 青青久久精品国产免费看| 亚洲国产另类久久久精品| 国产精品成人99久久久久91gav| 久久久久亚洲AV无码观看| 国内精品久久国产大陆| 一本色道久久88综合日韩精品 | 亚洲国产成人精品女人久久久| 伊人久久无码中文字幕| 精品久久久久中文字| 国产精品久久影院| 亚洲午夜久久久久妓女影院 | 亚洲国产精品无码久久一区二区| 四虎国产精品免费久久久| 久久亚洲精品无码AV红樱桃| 2021国产精品久久精品| 99久久中文字幕| AV无码久久久久不卡蜜桃| 免费一级欧美大片久久网| 99久久精品无码一区二区毛片 | yy6080久久| 欧美午夜A∨大片久久 | 国产—久久香蕉国产线看观看 | 久久天天躁狠狠躁夜夜2020| 国产精品成人精品久久久| 伊人久久大香线蕉精品| 欧美伊香蕉久久综合类网站| 久久综合久久综合久久| 国产99久久精品一区二区| 69国产成人综合久久精品| 精品久久久久久国产| 国产一区二区精品久久岳| 久久99精品国产麻豆蜜芽| 久久天天躁狠狠躁夜夜不卡 | 欧美日韩精品久久免费|