首页 > 代码库 > POJ2442——Squence（二叉堆+动态规划 | 滚动数组）
POJ2442——Squence（二叉堆+动态规划 | 滚动数组）
本文出自：http://blog.csdn.net/svitter
题意分析：
Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It‘s clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?
给你m个序列，每个包含n个非负的整数。现在我们需要从每一个序列中选择一个整数。我们可以很简单的得出一个一共有n^m个组合。我们可以计算出每个序列的加和，并且得到n^m组值。我们需要n组最小序列和。
输入输出分析：
The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.
给T组测试样例。第一行包括两个整数m，n分别代表m个序列， n个整数。没有整数大于10000（没有超过int）
算法数据结构分析：
AC代码：
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 2010
int m, n;
int t;
int a[2][MAXN];
int main()
{
int i, j, k;
int c;
int temp1, temp2;
freopen("test/test2", "r", stdin);
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &m, &n);
for(i = 0; i < n; i++)
scanf("%d", &a[0][i]);
make_heap(a[0], a[0]+n);
c = 0;
for(i = 1; i < m; i++, c = 1-c)
{
scanf("%d", &temp1);
for(k = 0; k < n; k++)
a[1-c][k] = a[c][k] + temp1;
for(k = 1; k < n; k++)
{
scanf("%d", &temp1);
for(j = 0; j < n; j++)
{
temp2 = a[c][j] + temp1;
if(temp2 < a[1-c][0])
{
pop_heap(a[1-c], a[1-c]+n);
a[1-c][n-1] = temp2;
push_heap(a[1-c], a[1-c]+n);
}
}
}
}
sort(a[c], a[c]+n);
for(i = 0; i < n-1; i++)
printf("%d ", a[c][i]);
printf("%d\n", a[c][n-1]);
}
return 0;
}