2017.07.13【NOIP提高組】模擬賽B組 服務器 題解

原題:

http://172.16.0.132/senior/#contest/show/2055/2

題目描述:

我們需要將一個文件復制到n個服務器上,這些服務器的編號為S1, S2, …, Sn。
首先掺出,我們可以選擇一些服務器翎承,直接把文件復制到它們中;將文件復制到服務器Si上,需要花費ci > 0的置放費用豁陆。對于沒有直接被復制文件的服務器Si來說篇裁,它依次向后檢查Si+1, Si+2, …直到找到一臺服務器Sj:Sj中的文件是通過直接復制得到的沛慢,于是Si從Sj處間接復制得到該文件,這種復制方式的讀取費用是j – i(注意j>i)达布。另外团甲,Sn中的文件必須是通過直接復制得到的,因為它不可能間接的通過別的服務器進行復制黍聂。我們設計一種復制方案躺苦,即對每一臺服務器確定它是通過直接還是間接的方式進行復制(Sn只能通過直接方式),最終使每一臺服務器都得到文件产还,且總花費最小匹厘。

輸入:

輸入文件的第一行有一個整數(shù)n,表示服務器的數(shù)目脐区。輸入文件的第二行有n個整數(shù)愈诚,順數(shù)第i個表示ci:在Si上直接復制文件的費用

輸出:

輸出文件中只包含一個整數(shù),即最少需要花費的費用牛隅。

樣例輸入:

10
2 3 1 5 4 5 6 3 1 2

樣例輸出:

18

數(shù)據(jù)范圍限制:

60%的數(shù)據(jù)中炕柔,1 <= n <= 1 000
100%的數(shù)據(jù)中,1 <= n <= 1 000 000
80%的數(shù)據(jù)中倔叼, 1 <= ci <= 50
100%的數(shù)據(jù)中汗唱,1 <= ci <= 1 000 000 000
最終結(jié)果可能較大,請注意選擇適當?shù)臄?shù)據(jù)類型進行計算丈攒。

提示:

77H+R6byQ4rtteAAAAAElFTkSuQmCC.png

分析:

dp
設f[i,0]表示第i個機器直接復制哩罪,f[i,1]表示第i個機器間接復制授霸,
f[n,0]=c[n];
很明顯,轉(zhuǎn)移方程為:
f[i,0]=min(f[i+1,0],f[i+1,1])+c[i];
f[i,1]=min(f[i,1],f[j,1]+(j-i-1)*(j-i)/2);
然后用隊列優(yōu)化即可

實現(xiàn):

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,i,j;
long long ans,f[1000001][2],s[1000001],t[1000001],c[1000001];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&c[i]);
    memset(f,127,sizeof(f));
    f[n][0]=c[n];
    s[++s[0]]=f[n][0];
    t[s[0]]=n;
    for(i=n-1;i;i--)
    {
        f[i][0]=min(f[i+1][0],f[i+1][1])+c[i];
        for(j=s[0];j;j--)
        {
            ans=(t[j]-i+1)*(t[j]-i)/2;
            if(ans>=f[i][1]) break;
            f[i][1]=min(f[i][1],s[j]+ans);
        }
        while(s[s[0]]>=f[i][0] && s[0]) s[0]--;
        s[++s[0]]=f[i][0];
        t[s[0]]=i;
    }
    printf("%lld",min(f[1][1],f[1][0]));
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末际插,一起剝皮案震驚了整個濱河市碘耳,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌框弛,老刑警劉巖辛辨,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異瑟枫,居然都是意外死亡斗搞,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進店門慷妙,熙熙樓的掌柜王于貴愁眉苦臉地迎上來僻焚,“玉大人,你說我怎么就攤上這事膝擂÷瞧。” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵架馋,是天一觀的道長狞山。 經(jīng)常有香客問我,道長叉寂,這世上最難降的妖魔是什么萍启? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮屏鳍,結(jié)果婚禮上伊约,老公的妹妹穿的比我還像新娘。我一直安慰自己孕蝉,他們只是感情好屡律,可當我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著降淮,像睡著了一般超埋。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上佳鳖,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天霍殴,我揣著相機與錄音,去河邊找鬼系吩。 笑死来庭,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的穿挨。 我是一名探鬼主播月弛,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼肴盏,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了帽衙?” 一聲冷哼從身側(cè)響起菜皂,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎厉萝,沒想到半個月后恍飘,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡谴垫,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年章母,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片翩剪。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡胳施,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出肢专,到底是詐尸還是另有隱情,我是刑警寧澤焦辅,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布博杖,位于F島的核電站,受9級特大地震影響筷登,放射性物質(zhì)發(fā)生泄漏剃根。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一前方、第九天 我趴在偏房一處隱蔽的房頂上張望狈醉。 院中可真熱鬧,春花似錦惠险、人聲如沸苗傅。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽渣慕。三九已至,卻和暖如春抱慌,著一層夾襖步出監(jiān)牢的瞬間逊桦,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工抑进, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留强经,地道東北人。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓寺渗,卻偏偏與公主長得像匿情,于是被迫代替她去往敵國和親兰迫。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 個人學習批處理的初衷來源于實際工作码秉;在某個迭代版本有個BS(安卓手游模擬器)大需求逮矛,從而在測試過程中就重復涉及到...
    Luckykailiu閱讀 4,734評論 0 11
  • Ubuntu的發(fā)音 Ubuntu府蔗,源于非洲祖魯人和科薩人的語言晋控,發(fā)作 oo-boon-too 的音。了解發(fā)音是有意...
    螢火蟲de夢閱讀 99,374評論 9 467
  • ¥開啟¥ 【iAPP實現(xiàn)進入界面執(zhí)行逐一顯】 〖2017-08-25 15:22:14〗 《//首先開一個線程姓赤,因...
    小菜c閱讀 6,451評論 0 17
  • 書評1《活著》 突然想起屌絲揚曾說赡译,讀書是提升逼格最廉價的途徑。想來不铆,因為各種事情蝌焚,已經(jīng)很久沒有靜心看書了。偶然整...
    阿木_e227閱讀 440評論 0 0
  • 1.text-align: center的作用是什么誓斥,作用在什么元素上只洒?能讓什么元素水平居中? 是塊級元素中的行內(nèi)...
    饑人谷_有點熱閱讀 316評論 0 0