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

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>
            黄色成人av网| 国产中文一区| 国产精品99久久99久久久二8| 亚洲高清网站| 欧美精品久久久久久久| 亚洲香蕉在线观看| 午夜精品久久久久久久99樱桃 | 亚洲视频久久| 国产视频精品xxxx| 欧美成人亚洲成人| 欧美日韩国产系列| 久久激情视频久久| 免费久久99精品国产自在现线| 99riav久久精品riav| 亚洲欧美卡通另类91av| 好看的日韩av电影| 亚洲黄色在线看| 国产精品国产三级国产aⅴ入口 | 亚洲一级黄色av| 欧美在线观看视频一区二区三区| 亚洲国产片色| 亚洲免费在线看| 亚洲国产人成综合网站| 亚洲一区二区精品| 亚洲国产精品国自产拍av秋霞| 亚洲精品影院| 国产有码一区二区| avtt综合网| 亚洲一二区在线| 影音先锋亚洲视频| 艳女tv在线观看国产一区| 国精品一区二区| 日韩午夜免费| 亚洲精品国产视频| 久久久精品免费视频| 国产精品99久久久久久有的能看| 久久精品国产一区二区三| 夜夜嗨av一区二区三区免费区| 欧美在线综合| 翔田千里一区二区| 欧美日韩免费视频| 欧美成年视频| 国内精品国语自产拍在线观看| 一区二区高清| av成人福利| 久久只精品国产| 久久九九精品99国产精品| 欧美日韩一二三区| 亚洲国产精品一区制服丝袜 | 欧美日韩一区二区欧美激情| 麻豆freexxxx性91精品| 国产视频亚洲精品| 亚洲网址在线| 亚洲综合成人婷婷小说| 欧美日韩一区二区三区在线观看免 | 久久色中文字幕| 久久久久久亚洲精品中文字幕| 国产精品久久久久久久久久免费看 | 亚洲小说春色综合另类电影| 亚洲色图自拍| 欧美日韩成人| 亚洲最新在线| 亚洲砖区区免费| 国产精品高潮在线| 亚洲一区二区视频在线观看| 亚洲在线视频观看| 国产精品vip| 亚洲一区制服诱惑| 久久国产福利国产秒拍| 国产午夜精品麻豆| 久久久www| 欧美激情视频一区二区三区免费 | 欧美jizz19hd性欧美| 欧美韩国日本一区| 亚洲精品在线观看视频| 欧美理论视频| 一本一本久久a久久精品综合麻豆 一本一本久久a久久精品牛牛影视 | 午夜精品99久久免费| 久久久国产精品一区二区三区| 国产综合色产| 牛牛国产精品| 一区二区激情视频| 久久久久成人精品| 91久久精品一区二区别| 欧美午夜一区二区| 久久不见久久见免费视频1| 免费成人在线视频网站| 日韩西西人体444www| 国产精品久久久久久久久免费| 亚洲欧美综合另类中字| 欧美国产精品日韩| 亚洲综合成人婷婷小说| 国内精品视频在线播放| 免费观看一区| 亚洲一区999| 欧美 亚欧 日韩视频在线| 一区二区免费在线播放| 国产乱码精品一区二区三区五月婷 | 国产精品成人在线观看| 欧美一区深夜视频| 最新高清无码专区| 欧美一区在线视频| 亚洲精品国产精品乱码不99按摩 | 久久久91精品| 99国产精品一区| 久久综合九色| 亚洲欧美日韩在线高清直播| 亚洲第一综合天堂另类专| 欧美亚洲免费高清在线观看| 欧美a级大片| 久久不射网站| 亚洲一区二区三区精品在线| 在线播放精品| 国产欧美短视频| 欧美精品手机在线| 噜噜噜躁狠狠躁狠狠精品视频| 在线综合+亚洲+欧美中文字幕| 免费av成人在线| 久久精品国产免费看久久精品| 日韩亚洲一区二区| 1769国内精品视频在线播放| 国产精品午夜电影| 欧美日韩午夜在线视频| 欧美h视频在线| 麻豆成人综合网| 久久久另类综合| 欧美在线啊v一区| 亚洲一区影音先锋| 制服丝袜亚洲播放| 日韩午夜免费视频| 亚洲精品乱码久久久久久黑人 | 亚洲国产91精品在线观看| 久久久综合网站| 久久久久国产成人精品亚洲午夜| 亚洲欧美成人| 亚洲一二三四久久| 亚洲在线观看免费视频| 亚洲夜晚福利在线观看| 亚洲视频狠狠| 亚洲视频中文| 亚洲午夜未删减在线观看| 亚洲天堂激情| 亚洲综合色自拍一区| 亚洲欧美www| 午夜精品久久久久久久99水蜜桃| 亚洲在线不卡| 性欧美video另类hd性玩具| 午夜亚洲一区| 欧美中文在线观看国产| 久久久久久久91| 久久午夜视频| 欧美福利视频在线观看| 91久久极品少妇xxxxⅹ软件| 亚洲人成网站影音先锋播放| 亚洲精品之草原avav久久| 99国产精品视频免费观看| 一区二区日韩| 欧美一乱一性一交一视频| 久久精品国产亚洲精品| 久久中文字幕一区| 欧美精品日日鲁夜夜添| 国产精品久久久久久久久免费樱桃 | 国产精品国产三级国产a| 国产日产欧产精品推荐色 | 亚洲免费观看| 亚洲欧美第一页| 久久激情视频| 亚洲欧洲精品一区二区三区| 亚洲深夜影院| 久久手机免费观看| 欧美日产在线观看| 国产亚洲精品v| 亚洲欧洲精品一区二区精品久久久| 一本久久a久久免费精品不卡| 亚洲永久免费精品| 久久手机精品视频| 亚洲人精品午夜| 亚洲欧美一区二区精品久久久| 久久免费少妇高潮久久精品99| 欧美成在线观看| 欧美日韩亚洲国产一区| 精品999网站| 亚洲资源av| 欧美激情第9页| 午夜视频久久久久久| 一本久久a久久精品亚洲| 亚洲欧美精品在线观看| 欧美高清在线一区| 国产自产2019最新不卡| 亚洲一区二区免费看| 欧美大片在线观看一区| 亚洲理论电影网| 久久综合中文色婷婷| 国产视频一区欧美| 亚洲一区二区三区四区中文| 麻豆成人av| 欧美一区二区日韩| 国产精品久久久久久久久久免费 | 久久伊人一区二区| 亚洲欧美精品中文字幕在线|