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）
