來自Facebook算法比賽的題目(PieProgress)

HackerCup

FacobookHackerCup是facebook下面的一個算法比賽岭埠,始于2011年巩踏,每年舉辦一屆。來自世界各地的coder都能夠參加該項比賽望几。在前兩天,HackCup剛進行完Round1萤厅,Round1有4個題目橄抹,分別為10,25,25,40分,得到35分以上晉級下一輪惕味。今天我們來看這個10分的題目楼誓。

Paste_Image.png

題目大意

Pie特別好吃,所以你每天都要吃一個名挥。
在接下來的N天疟羹,你每天都會去買Pie,每天都會有M個Pie出售,第i天的第j個pie的售價為c[i][j],在這個神奇的國度禀倔,如果你一天買x個Pie,那么你就要給x^2的稅榄融。
Pie很特殊,很難過期救湖,所以可以存放無限久愧杯,問最少要花多少錢,才能保證每天吃上一個Pie.

樣例輸入

第一行是一個數(shù)T,表示有T組樣例鞋既,接下來兩個數(shù)力九,N,M表示N天,每天有M個Pie出售邑闺,接下來一個N*M的矩陣跌前,表示第i天第j個Pie的售價。


樣例輸出


第一個樣例陡舅,我們第一天買2個Pie抵乓,花費是1 + 1 + 2 * 2 = 6元,第2天買一個Pie,花費101元,總共107元灾炭。

原題

思考

解法一:

首先我們先對這個問題進行抽象章鲤,我們用f[i][j]表示從第1天到第i天,累計買了j個Pie花費的最低價錢咆贬,為了保證每天吃上一個Pie,我們需要保證j >= i, 最后求F[N][N]帚呼。
如果我們從f[i][j]轉(zhuǎn)移到f[i + 1][k],兩者之間的差值就是cost[i + 1][k - j]掏缎,它的含義是第i+1天,買了k - j 個Pie的最小花費煤杀。(0 <= k-j <=M.)
那么這個cost[i + 1][k - j]怎么求呢眷蜈?非常的簡單,我們需要把第i+1天的Pie從小到大進行排序沈自,然后就能求出對應(yīng)的結(jié)果酌儒。cost[i][j] = Sigma{a[i][j']} + j * j.
我們總結(jié)一下動態(tài)規(guī)劃的轉(zhuǎn)移方程:
f[i][j] = Math.min{f[i - 1][j - k] + cost[i][k]},j >= i, k <= min(j, M);

解法二:

這個解法是剛剛寫這個文章才想到的,這個題目枯途,我們可以逆向地看待這個問題忌怎,原題可以等價于,最后一天酪夷,最少需要買1個餅榴啸,我們從最后一天去考慮,到了倒數(shù)第二天晚岭,我們連著最后一天鸥印,最少需要買2個餅,到了倒數(shù)第三天坦报,最少需要買3個餅库说,如果倒數(shù)第3天的餅比倒數(shù)第二天或者第一天的劃算,那么我們就能把后面的替換掉片择。
問題等價于維護一個大根堆潜的!我們又考慮到了餅是有稅的,但是這個餅的稅是可以進行轉(zhuǎn)化的构回,假設(shè)某一天的餅的花費為a[0]..a[M -1]夏块,我們從小到大排序后,把稅加上去纤掸,第1個餅的花費為a[0] + 1 * 1,第2個餅的花費為a[1] + 2 * 2 - 1 * 1, 第3個餅的花費為a[2] + 3 * 3 - 2 * 2...
我們用這種做法來解決第一個樣例脐供,第3天,選擇一個餅借跪,堆里面的元素有10001政己,第2天,選擇一個餅掏愁,堆里面的元素為101, 10001,我們發(fā)現(xiàn)第2天第2個餅的價值103小于10001鲁纠,所以替換掉骄酗,堆里面的元素變成101, 103.到了第一天轴捎,我們先去最小的2加入堆,然后再用4替換掉103,堆中元素變成2,4,101释牺,最后的結(jié)果就是107了。

代碼

當(dāng)時其實我只想到第一種解法回挽,所以看這個代碼吧没咙。

第33-41行,預(yù)處理第i天買j個餅的最小花費
第43-55行千劈,動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移祭刚,注意考慮邊界條件,這里我把初始值都弄成-1墙牌,如果弄成一個夠大的數(shù)可以減少那個if涡驮。

AD

歡迎關(guān)注我的公眾號(ddpcyh)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市喜滨,隨后出現(xiàn)的幾起案子遮怜,更是在濱河造成了極大的恐慌,老刑警劉巖鸿市,帶你破解...
    沈念sama閱讀 216,744評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件锯梁,死亡現(xiàn)場離奇詭異,居然都是意外死亡焰情,警方通過查閱死者的電腦和手機陌凳,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,505評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來内舟,“玉大人合敦,你說我怎么就攤上這事⊙橛危” “怎么了充岛?”我有些...
    開封第一講書人閱讀 163,105評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長耕蝉。 經(jīng)常有香客問我崔梗,道長,這世上最難降的妖魔是什么垒在? 我笑而不...
    開封第一講書人閱讀 58,242評論 1 292
  • 正文 為了忘掉前任蒜魄,我火速辦了婚禮,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘谈为。我一直安慰自己旅挤,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 67,269評論 6 389
  • 文/花漫 我一把揭開白布伞鲫。 她就那樣靜靜地躺著粘茄,像睡著了一般。 火紅的嫁衣襯著肌膚如雪秕脓。 梳的紋絲不亂的頭發(fā)上驹闰,一...
    開封第一講書人閱讀 51,215評論 1 299
  • 那天,我揣著相機與錄音撒会,去河邊找鬼。 笑死师妙,一個胖子當(dāng)著我的面吹牛诵肛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播默穴,決...
    沈念sama閱讀 40,096評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼怔檩,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了蓄诽?” 一聲冷哼從身側(cè)響起薛训,我...
    開封第一講書人閱讀 38,939評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎仑氛,沒想到半個月后乙埃,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,354評論 1 311
  • 正文 獨居荒郊野嶺守林人離奇死亡锯岖,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,573評論 2 333
  • 正文 我和宋清朗相戀三年介袜,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片出吹。...
    茶點故事閱讀 39,745評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡遇伞,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出捶牢,到底是詐尸還是另有隱情鸠珠,我是刑警寧澤,帶...
    沈念sama閱讀 35,448評論 5 344
  • 正文 年R本政府宣布秋麸,位于F島的核電站渐排,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏灸蟆。R本人自食惡果不足惜飞盆,卻給世界環(huán)境...
    茶點故事閱讀 41,048評論 3 327
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧吓歇,春花似錦孽水、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,683評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至测柠,卻和暖如春炼鞠,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背轰胁。 一陣腳步聲響...
    開封第一講書人閱讀 32,838評論 1 269
  • 我被黑心中介騙來泰國打工谒主, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人赃阀。 一個月前我還...
    沈念sama閱讀 47,776評論 2 369
  • 正文 我出身青樓霎肯,卻偏偏與公主長得像,于是被迫代替她去往敵國和親榛斯。 傳聞我的和親對象是個殘疾皇子观游,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,652評論 2 354

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

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪:刷leetcod...
    土汪閱讀 12,743評論 0 33
  • thiele插值算法 1點插值算法 function [C,c]=thiele(X,Y,Z)%X為插值點橫坐標驮俗,Y...
    00crazy00閱讀 1,989評論 0 4
  • Java經(jīng)典問題算法大全 /*【程序1】 題目:古典問題:有一對兔子懂缕,從出生后第3個月起每個月都生一對兔子,小兔子...
    趙宇_阿特奇閱讀 1,863評論 0 2
  • 樹形動態(tài)規(guī)劃王凑,顧名思義就是樹+DP搪柑,先分別回顧一下基本內(nèi)容吧:動態(tài)規(guī)劃:問題可以分解成若干相互聯(lián)系的階段,在每一個...
    Mr_chong閱讀 1,484評論 0 2
  • 每天我們都會使用到各種各樣的app十歲的女兒已經(jīng)可用各種app應(yīng)對生活中的各種事情我們沒法逃避也沒法拒絕我們生活在...
    哈哈同學(xué)閱讀 247評論 0 0