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