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

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>
            亚洲一区二区三区在线播放| 亚洲三级免费观看| 欧美一区二区精美| 亚洲男女毛片无遮挡| 国产精品亚洲成人| 久久精品国产2020观看福利| 欧美一区二区三区在线看| 国产色婷婷国产综合在线理论片a| 性久久久久久久久久久久| 欧美一区二区三区四区在线观看地址| 国语精品一区| 91久久香蕉国产日韩欧美9色| 欧美成人在线免费观看| 99爱精品视频| 小黄鸭视频精品导航| 亚洲电影网站| 一区二区三区国产| 激情丁香综合| 一区二区三区视频在线看| 国内自拍一区| 一区二区不卡在线视频 午夜欧美不卡在 | 欧美一区二区大片| 亚洲激情啪啪| 亚洲欧美日韩高清| 亚洲全部视频| 欧美一级黄色录像| 99视频在线观看一区三区| 国产一区二区三区免费在线观看 | 亚洲最新在线视频| 欧美一级久久| 亚洲资源av| 久久综合999| 午夜亚洲精品| 欧美劲爆第一页| 免费成人av| 国产精品日本精品| 亚洲三级网站| 亚洲国产欧美一区二区三区同亚洲| 亚洲图片欧美一区| 99re6这里只有精品| 久久精品国产清自在天天线| 亚洲在线观看视频网站| 免费成人av资源网| 欧美在线91| 国产精品国产三级国产普通话三级| 欧美成人一区二区三区在线观看| 国产欧美在线观看一区| 99视频一区二区三区| 亚洲日本无吗高清不卡| 久久尤物电影视频在线观看| 久久国产精品亚洲77777| 国产精品你懂的在线| 亚洲三级免费| 99re66热这里只有精品3直播 | 亚洲一区二区三区四区中文| 一区二区三区免费在线观看| 欧美成人一区二区三区在线观看| 美女亚洲精品| 在线精品国产欧美| 久久久精品国产免大香伊| 久久精品日韩| 国模私拍一区二区三区| 欧美自拍偷拍| 美日韩精品视频| 在线成人中文字幕| 久久综合亚洲社区| 欧美大秀在线观看| 91久久久一线二线三线品牌| 狂野欧美激情性xxxx欧美| 欧美a级理论片| 亚洲三级免费电影| 欧美人与性动交α欧美精品济南到| 最新精品在线| 亚洲一区三区电影在线观看| 国产精品美女| 久久成人这里只有精品| 欧美大片一区二区| 亚洲美女淫视频| 欧美少妇一区| 亚洲欧美日韩国产综合精品二区| 久久av一区二区| 一区二区在线免费观看| 蜜桃久久av| 一区二区免费看| 久久久www成人免费毛片麻豆| 黄色一区三区| 欧美激情中文字幕乱码免费| 亚洲素人一区二区| 老妇喷水一区二区三区| 99国产精品久久久| 欧美高清视频免费观看| 中文网丁香综合网| 国产老肥熟一区二区三区| 久久国产成人| 99精品国产一区二区青青牛奶| 欧美一区二区三区视频在线观看| 欲香欲色天天天综合和网| 欧美a级在线| 亚欧成人在线| 亚洲乱码一区二区| 久久精品国产96久久久香蕉| 亚洲日本欧美在线| 国产日韩高清一区二区三区在线| 牛牛国产精品| 午夜视频一区| 亚洲美女视频在线免费观看| 久久久噜噜噜久久中文字幕色伊伊| 亚洲毛片一区二区| 国内精品写真在线观看| 欧美日韩视频在线第一区| 久久国产精品亚洲77777| 日韩视频在线永久播放| 你懂的成人av| 久久精品国产亚洲一区二区| 亚洲免费av片| 一区二区在线看| 国产日韩欧美电影在线观看| 欧美日本三区| 欧美成人午夜视频| 欧美一级久久久| 亚洲一区二区黄| 亚洲美女在线视频| 欧美成人蜜桃| 久久综合精品国产一区二区三区| 亚洲欧美日韩在线播放| 亚洲最新在线| 夜夜嗨av一区二区三区四区| 亚洲激情在线视频| 狠色狠色综合久久| 国产日韩欧美不卡| 国产欧美日韩视频在线观看| 欧美三区免费完整视频在线观看| 欧美高清hd18日本| 麻豆九一精品爱看视频在线观看免费| 久久国产视频网| 欧美专区在线| 欧美在线视频在线播放完整版免费观看 | 久久艳片www.17c.com| 久久av二区| 久久精品国产69国产精品亚洲 | 一区二区三区.www| 日韩视频免费| 一区二区三区欧美| 一区二区三区免费看| 亚洲网站视频| 亚洲欧美国产精品桃花| 亚洲影院在线| 欧美在线视频观看| 久久精品国产99国产精品澳门| 欧美一区免费| 久久免费视频在线观看| 久久综合导航| 欧美激情中文字幕一区二区| 欧美成人午夜激情视频| 欧美成人中文| 亚洲精品免费电影| 在线中文字幕一区| 亚洲综合日本| 久久亚洲国产成人| 欧美精品久久一区| 国产精品h在线观看| 国产日韩欧美精品一区| 在线欧美小视频| 99riav久久精品riav| 午夜精品久久久久久久99樱桃| 久久精品理论片| 欧美激情按摩| 亚洲一区二区三区高清| 久久精品30| 欧美日韩激情小视频| 国产欧美日韩一区二区三区| 亚洲国产精品激情在线观看| 在线视频中文亚洲| 欧美在线|欧美| 亚洲激情亚洲| 小嫩嫩精品导航| 欧美激情视频免费观看| 国产农村妇女毛片精品久久莱园子| 在线观看日韩av| 亚洲一区高清| 噜噜噜噜噜久久久久久91 | 欧美成人免费在线视频| 亚洲视频碰碰| 欧美不卡视频一区| 国产深夜精品福利| 亚洲视频一区在线| 免费亚洲一区二区| 亚洲影院色无极综合| 欧美激情精品久久久久久大尺度 | 久久精品国产亚洲一区二区三区 | 久久精品国产久精国产思思| 欧美精品成人一区二区在线观看 | 国产美女搞久久| 亚洲人午夜精品免费| 久久久久久九九九九| 亚洲精品视频免费观看| 久久久水蜜桃av免费网站| 国产精品婷婷| 亚洲一区二区三区精品视频| 亚洲国产精品小视频|