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.
样例输入
第一行是一个数T,表示有T组样例，接下来两个数，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]转移到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从小到大进行排序，然后就能求出对应的结果。cost[i][j] = Sigma{a[i][j']} + j * j.
我们总结一下动态规划的转移方程：
f[i][j] = Math.min{f[i - 1][j - k] + cost[i][k]},j >= i, k <= min(j, M);
解法二：
这个解法是刚刚写这个文章才想到的，这个题目，我们可以逆向地看待这个问题，原题可以等价于，最后一天，最少需要买1个饼，我们从最后一天去考虑，到了倒数第二天，我们连着最后一天，最少需要买2个饼，到了倒数第三天，最少需要买3个饼，如果倒数第3天的饼比倒数第二天或者第一天的划算，那么我们就能把后面的替换掉。
问题等价于维护一个大根堆！我们又考虑到了饼是有税的，但是这个饼的税是可以进行转化的，假设某一天的饼的花费为a[0]..a[M -1]，我们从小到大排序后，把税加上去，第1个饼的花费为a[0] + 11,第2个饼的花费为a[1] + 22 - 11, 第3个饼的花费为a[2] + 33 - 2 * 2...
我们用这种做法来解决第一个样例，第3天，选择一个饼，堆里面的元素有10001，第2天，选择一个饼，堆里面的元素为101， 10001，我们发现第2天第2个饼的价值103小于10001，所以替换掉，堆里面的元素变成101， 103.到了第一天，我们先去最小的2加入堆，然后再用4替换掉103，堆中元素变成2,4,101，最后的结果就是107了。
代码
当时其实我只想到第一种解法，所以看这个代码吧。
第33-41行，预处理第i天买j个饼的最小花费
第43-55行，动态规划状态转移，注意考虑边界条件，这里我把初始值都弄成-1，如果弄成一个够大的数可以减少那个if。
AD
欢迎关注我的公众号（ddpcyh）
