青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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.


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

 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 閱讀(1447) 評論(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 是死活進不去了,太弱了……
  回復  更多評論   

導航

<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

統計

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产乱码精品一区二区三区五月婷 | 国产精品久久一区主播| 日韩网站免费观看| 亚洲靠逼com| 国产精品爽黄69| 久久亚洲国产精品一区二区| 久久精品视频一| 日韩午夜电影在线观看| 在线视频你懂得一区| 国产日韩在线看片| 欧美激情综合| 欧美亚日韩国产aⅴ精品中极品| 欧美亚洲一级| 老牛影视一区二区三区| 正在播放亚洲一区| 欧美一区激情| 一区二区三区不卡视频在线观看| 一区二区三区**美女毛片| 国产午夜精品在线观看| 亚洲高清资源综合久久精品| 欧美精品一区二区三区很污很色的 | 久久综合精品国产一区二区三区| 亚洲乱码日产精品bd| 亚洲一区视频在线| 亚洲精品国精品久久99热| 亚洲一区二区免费在线| 在线成人中文字幕| 亚洲午夜电影在线观看| 亚洲福利一区| 亚洲欧美99| aⅴ色国产欧美| 久久青草欧美一区二区三区| 亚洲无限乱码一二三四麻| 久久久亚洲人| 欧美在线欧美在线| 欧美三日本三级少妇三2023 | 美腿丝袜亚洲色图| 欧美四级剧情无删版影片| 免费成人av资源网| 国产女人水真多18毛片18精品视频| 欧美国产大片| 极品中文字幕一区| 亚洲一二三区在线| 亚洲视频香蕉人妖| 欧美精品国产精品| 亚洲电影av| 亚洲电影在线免费观看| 欧美一级一区| 久久国产色av| 国产深夜精品| 亚洲欧美国产制服动漫| 亚洲小视频在线观看| 欧美日韩高清在线观看| 欧美成人一区二区三区| 影音先锋久久久| 久久精品国产欧美激情| 久久福利资源站| 亚洲精品久久嫩草网站秘色| 在线观看91精品国产麻豆| 欧美专区中文字幕| 久久伊人免费视频| 激情文学综合丁香| 久久激情五月丁香伊人| 久久国产精品久久国产精品| 国产精品免费视频观看| 亚洲一区二区三区四区五区午夜| 亚洲影音一区| 国产日韩亚洲| 久久久精品五月天| 蜜臀av一级做a爰片久久| 亚洲电影观看| 欧美日本免费| 亚洲午夜在线观看视频在线| 亚洲欧美一区二区三区久久 | 国产麻豆成人精品| 欧美一级理论性理论a| 久久精品三级| 亚洲人成毛片在线播放女女| 欧美国产日韩精品| av成人免费在线观看| 欧美一级理论片| 黄色成人小视频| 欧美电影打屁股sp| 一区二区欧美亚洲| 久久久中精品2020中文| 亚洲精品久久| 国产精品久久一级| 久久午夜av| 日韩视频第一页| 久久精品在线观看| 亚洲人成在线播放| 国产精品免费一区二区三区观看| 欧美亚洲网站| 亚洲国产视频直播| 午夜亚洲福利在线老司机| 一区二区亚洲精品| 欧美日韩亚洲综合一区| 欧美中文字幕视频在线观看| 亚洲高清不卡在线观看| 性欧美长视频| 亚洲美女在线看| 国产丝袜一区二区| 欧美日本精品在线| 久久躁日日躁aaaaxxxx| 中日韩美女免费视频网址在线观看 | 国产一区二区精品| 欧美理论视频| 久久久综合视频| 亚洲综合第一| 日韩亚洲欧美综合| 欧美成人免费视频| 久久精品三级| 午夜视频在线观看一区| 亚洲区中文字幕| 国内成人自拍视频| 国产精品户外野外| 欧美国产日韩亚洲一区| 久久精品视频在线播放| 亚洲视频欧美视频| 亚洲黄色在线| 免费日韩成人| 久久久蜜桃一区二区人| 欧美区一区二区三区| 久久综合999| 久久久久88色偷偷免费| 亚洲欧美综合国产精品一区| 亚洲看片网站| 亚洲精品久久嫩草网站秘色| 暖暖成人免费视频| 久久久午夜电影| 久久精品国产一区二区三| 亚洲男人的天堂在线aⅴ视频| 亚洲日本在线视频观看| 在线成人激情黄色| 伊人成人开心激情综合网| 国产欧美日韩精品专区| 国产精品久久一区二区三区| 欧美三日本三级少妇三2023| 欧美日韩国产欧| 欧美日韩国产美| 欧美日韩日韩| 国产精品v日韩精品v欧美精品网站| 欧美日韩高清不卡| 欧美午夜一区二区| 国产精品成人一区二区艾草| 国产精品va在线| 国产乱人伦精品一区二区| 国产欧美日韩精品在线| 国产一区99| 在线观看亚洲精品| 亚洲精品国产精品国产自| 最新日韩中文字幕| 亚洲午夜在线视频| 欧美亚洲在线| 另类成人小视频在线| 欧美激情影院| 国产精品99久久99久久久二8| 亚洲综合国产精品| 久久精品视频免费| 欧美激情中文字幕在线| 国产精品久久久999| 国产亚洲欧美一区二区| 在线不卡欧美| 亚洲性视频h| 久久天堂国产精品| 亚洲精选视频免费看| 亚洲影音先锋| 免费国产一区二区| 国产精品极品美女粉嫩高清在线| 国产精品亚洲精品| 亚洲第一福利社区| 亚洲神马久久| 美女国产一区| 亚洲图片在线| 久久综合久久88| 国产精品久久一区二区三区| 伊人久久久大香线蕉综合直播| 一区二区欧美亚洲| 久久视频在线视频| 日韩亚洲欧美一区| 久久久午夜视频| 国产精品地址| 亚洲乱码国产乱码精品精可以看 | 欧美亚洲日本国产| 欧美精品成人91久久久久久久| 国产精品丝袜白浆摸在线| 亚洲国产欧美日韩精品| 午夜在线成人av| 亚洲看片网站| 免费成人小视频| 国产亚洲人成a一在线v站| 亚洲天堂男人| 亚洲日本va午夜在线影院| 香蕉精品999视频一区二区| 欧美日韩999| 亚洲精品国产欧美| 蜜臀久久99精品久久久久久9| 亚洲在线播放电影| 欧美日韩亚洲国产精品| 亚洲欧洲在线看|