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

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观看福利| 一区二区三区日韩精品视频| 免播放器亚洲一区| 一区免费观看| 亚洲人午夜精品| 欧美视频二区| 久久激情综合网| 久久综合电影一区| 日韩亚洲欧美成人| 亚洲自拍偷拍网址| 狠狠色伊人亚洲综合网站色| 欧美国产日本| 国产精品九九| 欧美成人午夜激情视频| 欧美日韩免费视频| 久久久激情视频| 欧美刺激午夜性久久久久久久| 亚洲一区在线看| 久久久久99| 亚洲主播在线观看| 久久久青草婷婷精品综合日韩 | 免费高清在线视频一区·| 国产精品99久久久久久www| 亚洲女同同性videoxma| 最新成人av网站| 亚洲欧洲av一区二区| 亚洲三级视频| 久久久福利视频| 这里只有精品视频| 久久综合色一综合色88| 亚洲在线播放| 欧美精品免费观看二区| 久久久久久久久久久一区| 欧美日韩高清不卡| 免费高清在线一区| 国产乱码精品| 日韩一级精品视频在线观看| 亚洲国产精品va在线看黑人| 亚洲女女女同性video| 日韩一级欧洲| 免费看精品久久片| 久久久久99| 国产精品三级久久久久久电影| 亚洲激情一区二区三区| 韩日精品视频| 欧美一区二区三区在| 亚洲伊人伊色伊影伊综合网| 欧美成人免费在线视频| 毛片一区二区三区| 国产日产欧产精品推荐色| 99精品视频一区| 一片黄亚洲嫩模| 欧美成人一区二区在线| 欧美成人午夜剧场免费观看| 经典三级久久| 久久久7777| 久久这里有精品15一区二区三区| 国产欧美日韩一区| 亚洲女性裸体视频| 午夜精品在线视频| 国产精品入口福利| 亚洲欧美制服中文字幕| 亚洲欧美日韩一区在线观看| 欧美午夜精品一区| 亚洲午夜精品久久久久久浪潮| 亚洲在线中文字幕| 国产精品男女猛烈高潮激情| 亚洲欧美成人综合| 久久国产日本精品| 一区二区三区在线不卡| 久久乐国产精品| 亚洲大胆女人| 一本色道久久| 国产精品日日摸夜夜添夜夜av | 亚洲日本国产| 亚洲综合电影一区二区三区| 国产精品久久久久久久第一福利 | 亚洲综合不卡| 久久久精品欧美丰满| 欧美刺激性大交免费视频| 最近看过的日韩成人| 欧美精品亚洲二区| 一区二区免费在线观看| 欧美怡红院视频| 一色屋精品亚洲香蕉网站| 美女国产一区| 野花国产精品入口| 久久久久国产精品www| 亚洲国产精品一区二区三区| 欧美片网站免费| 午夜精品亚洲| 亚洲激情成人网| 久久av一区二区三区漫画| 在线观看视频日韩| 欧美午夜视频在线| 久久久久久久久岛国免费| 亚洲国产精品专区久久| 亚久久调教视频| 亚洲精选成人| 国产偷国产偷精品高清尤物| 欧美大片免费观看在线观看网站推荐| 99国产成+人+综合+亚洲欧美| 久久精品五月婷婷| 一区二区三区久久久| 国产主播精品在线| 欧美日韩裸体免费视频| 久久成人羞羞网站| 99视频精品在线| 欧美成人乱码一区二区三区| 亚洲欧美国产高清va在线播| 亚洲二区在线视频| 国产一区91| 国产精品mv在线观看| 免费日韩成人| 久久久久久电影| 亚洲一区视频在线观看视频| 亚洲精选成人| 亚洲国产合集| 欧美1区视频| 久久久xxx| 欧美亚洲视频| 午夜日韩av| 亚洲无线视频| 夜夜嗨av色综合久久久综合网 | 国产精品社区| 欧美日韩一区二区在线观看视频| 老色鬼久久亚洲一区二区| 欧美在线网站| 欧美一级在线亚洲天堂| 亚洲男人第一av网站| 99国产精品久久久久久久成人热| 欧美国产视频一区二区| 美女精品在线观看| 久久夜色精品国产欧美乱极品| 久久国产精品99国产| 欧美一区国产在线| 性欧美1819sex性高清| 午夜精品久久久久久99热| 亚洲欧美激情视频| 亚洲一区二区三区乱码aⅴ蜜桃女| 日韩视频二区| 一区二区三区精密机械公司| 99成人精品| 亚洲综合色婷婷| 欧美亚洲在线视频| 欧美一区二区三区精品电影| 欧美一区二区三区免费大片| 久久成人免费| 久久亚洲视频| 亚洲国产精品电影| 亚洲蜜桃精久久久久久久| 日韩系列在线| 亚洲视频免费| 久久久精品日韩欧美| 免费成人美女女| 欧美精品免费播放| 国产精品久久久久久av下载红粉 | 国产视频精品免费播放| 国产手机视频精品| 在线精品国产成人综合| 日韩午夜av| 亚洲女爱视频在线| 久久久国产91| 最新亚洲一区| 午夜视频一区二区| 美国成人直播| 欧美午夜精品理论片a级大开眼界| 国产精品一区二区女厕厕| 国语自产精品视频在线看8查询8| 亚洲激情一区| 欧美一区二区三区四区夜夜大片 | 欧美一区二区三区免费观看视频| 久久久久久一区| 亚洲国产精品电影| 亚洲欧美日韩国产中文| 美日韩丰满少妇在线观看| 国产精品成人观看视频国产奇米| 国产精品自拍在线| 亚洲国产精品视频一区| 亚洲在线成人| 欧美激情一区| 午夜亚洲精品| 欧美日韩亚洲一区二区| 狠狠色狠色综合曰曰| 亚洲一线二线三线久久久| 老牛影视一区二区三区| 一区二区三区国产精品| 麻豆国产精品777777在线| 国产精品久久久久久五月尺| 亚洲人被黑人高潮完整版| 久久精品国产亚洲精品| 99re8这里有精品热视频免费| 久久久国产精品亚洲一区 | 亚洲国产精品一区二区三区| 欧美亚洲视频| 亚洲日本va午夜在线电影| 欧美综合国产| 国产精品一区二区三区久久| 99成人精品| 亚洲国产精品精华液网站|