K个最小和 (UVA 11997 K Smallest Sums)

题目大意:

You’re given k arrays, each array has k integers. There are k^k ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them.

Input

There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each test case, print the k smallest sums, in ascending order.

Sample Input

3
1 8 5
9 2 5
10 7 6
2
1 1
1 2

Output for the Sample Input

9 10 12
2 2

给定一个k*k的一个矩阵,如果让你在每一行取出一个数,再将每一行取出的数相加,那么总共可以得到k^k种相加方法,现在让你求出这k^k个结果中最小的k个结果。

分析与解法

仔细分析这个题目我们会发现其实这个问题是满足最优子结构的,比如:

如果我们已经计算出了前m行,每行取出一个数相加的最小的k个结果,分别是DP[1],DP[2]…DP[k] (注意这里的DP表示的是前m行每行一个相加的最小的前k个值)

假设第m+1行的值是A[1],A[2]…A[k] (注意这里的A[i]表示的是第m+1行的第i个数) 当我们推倒到第m+1行时,由于我们只计算了前m行的前k个最小值,那我们是不是有必要多计算一些来推导出第m+1行的前k个最小值呢?

答案是不必要的,我们可以通过以下数学公式严格证明:
设DP[x]是前m行通过计算得出的第x(x>k)小的和,如果上述的假设成立,那么我们可以列出不等式:

  1. DP[x] + A[y] < DP[m] + A[n] (1)
  2. (DP[m]+A[n]表示只通过DP[1,2...k]计算出的前m+1行第k小的和)

上述不等式的含义是指在第m+1行存在一个数A[y],使得DP[x]+A[y]是前m+1行中前k小的结果。
同时,我们注意到:

  1. x>k ==> DP[x] > DP[k] (2)
  2. A[y] >= A[1] (3)

由上面三个不等式(1),(2),(3)我们可以得到:

  1. DP[k]+A[1] <= DP[x]+A[y] < DP[m]+A[n]
  2. DP[k]+A[1] < DP[m]+A[n]

之前我们说过DP[m] + A[n] 是前m行第k大的和,然而:比DP[k]+A[1]小的数已经有

  1. DP[1]+A[1]),(DP[2]+A[1])...(DP[k-1]+A[1])共计k-1个,

所以DP[k]+A[1]是第k个最小的和,与假设的DP[m]+A[n]是第k个最小的和相矛盾,所以假设不成立。得证。

通过以上的证明我们可以得出结论要计算第m+1行的前k个最小和是只需要计算出前m行的前k个最小的和即可。这时,我们的目标就转化为了计算一个2*k的数组,在第一行取一个数,在第二行取一个数,得到k^2个和,求他们当中的最小的k个和。

为了计算它,我们把这n^2个数组织成如下n个有序表:

  1. 1 A1+B1 <= A1+B2<=A1+B3<=......
  2. 2 A2+B1 <= A2+B2<=A2+B3<=......
  3. .
  4. n An+B1 <= An+B2<=An+B3<=......

这时我们用一个二元组(sum, b)来保存以上的每一个元素,其中sum=A[a] + B[b].

为什么不保存A的下标a呢?因为我们用不到a的值。如果我们需要在表(sum, b)中赵到下一个元素(sum’, b+1),只要计算sum’ = s - B[b] + B[b+1],不需要知道a是多少。

实现代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. using namespace std;
  5. int a[800][800],k;
  6. struct node
  7. {
  8. int s,b;
  9. bool operator<(const node &a) const
  10. {
  11. return s>a.s;
  12. }
  13. };
  14. void merge(int *A,int *B,int *C,int n)
  15. {
  16. node tmp;
  17. priority_queue<node> q;
  18. for(int i=0;i<n;i++)
  19. {
  20. tmp.s=A[i]+B[0],tmp.b=0;
  21. q.push(tmp);
  22. }
  23. for(int i=0;i<n;i++)
  24. {
  25. tmp=q.top();
  26. q.pop();
  27. C[i]=tmp.s;
  28. if(tmp.b+1<n)
  29. {
  30. tmp.s=tmp.s-B[tmp.b]+B[tmp.b+1];
  31. tmp.b++;
  32. q.push(tmp);
  33. }
  34. }
  35. }
  36. int main()
  37. {
  38. while(~scanf("%d",&k))
  39. {
  40. for(int i=0;i<k;i++)
  41. {
  42. for(int j=0;j<k;j++)
  43. scanf("%d",&a[i][j]);
  44. sort(a[i],a[i]+k);
  45. }
  46. for(int i=1;i<k;i++)
  47. merge(a[0],a[i],a[0],k);
  48. for(int i=0;i<k;i++)
  49. printf("%d%s",a[0][i],i!=k-1?" ":"\n");
  50. }
  51. return 0;
  52. }

参考 http://www.cnblogs.com/gj-Acit/p/3583480.html