step1：贪心可以将问题分解成每次将最上面的两行合并得到最优解；
如果 a[i] + b[j] < a[i’] + b[j’] 那么 a[i] + b[j] + c[k] + .. < a[i’] + b[j’] + c[k] + .. 因此 每次合并前两行取出前n个元素，作为新的一行，可以得到最优解
step2：排序后，利用优先队列优化将两行合并的算法；
优先队列存储的数据如下：a[i]+b[j], a[i’]+b[j’], .. 队列中的元素，各含有一个不同的a[i]，每个a[i]对应当前的b[j] 整个过程像是一个矩阵，当前每个a[p]对应不同的b（图中的i，j，k），每次利用最小的a[p]+b[q]更新为a[i]+b[q+1]可以优化更新的效率，其实就是对应的b的指针后移了一位：
⎡⎣⎢⎢⎢⎢a0a1⋮an⎤⎦⎥⎥⎥⎥⎡⎣⎢⎢⎢⎢⎢b0b0⋮b0⋯⋯⋱⋯bi⋯⋯⋯⋯⋯⋯⋯⋯bj⋯⋯⋯⋯⋯⋯⋯⋯⋯bk⋯⋯⋯⋯bnbn⋮bn⎤⎦⎥⎥⎥⎥⎥ [ a 0 a 1 ⋮ a n ] [ b 0 ⋯ b i ⋯ ⋯ ⋯ ⋯ ⋯ b n b 0 ⋯ ⋯ ⋯ b j ⋯ ⋯ ⋯ b n ⋮ ⋱ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋮ b 0 ⋯ ⋯ ⋯ ⋯ ⋯ b k ⋯ b n ] 说明：到香港后的第一道题o( ￣︶￣)o。 #include <algorithm> #include <iostream> #include <cstdio> #include <queue> using namespace std; int data[755][755]; typedef struct _pq_node { int sum; int b_id; // save the id now used by a[i]; bool operator < (const _pq_node& n)const{ return sum > n.sum; } }pq_node; int main() { int n; while (~scanf("%d", &n)) { for (int i = 0; i < n; ++ i) { for (int j = 0; j < n; ++ j) { scanf("%d", &data[i][j]); } } // sort : n^2*ln(n) for (int i = 0; i < n; ++ i) { sort(data[i], data[i]+n); } priority_queue<pq_node> pq; pq_node Now, New; for (int i = 1; i < n; ++ i) { // clear pq while (!pq.empty()) { pq.pop(); } // put initial data into pq for (int j = 0; j < n; ++ j) { Now.sum = data[i][j] + data[i-1][0]; Now.b_id = 0; pq.push(Now); } for (int j = 0; j < n; ++ j) { Now = pq.top(); pq.pop(); data[i][j] = Now.sum; if (Now.b_id+1 < n) { New.sum = Now.sum - data[i-1][Now.b_id] + data[i-1][Now.b_id+1]; New.b_id = Now.b_id + 1; pq.push(New); } } } printf("%d", data[n-1][0]); for (int i = 1; i < n; ++ i) { printf(" %d", data[n-1][i]); } printf("\n"); } return 0; }