poj2442（Sequence）

题目地址：Sequence

题目大意;

     给你m行，每行有n个数。 分别从每一行取一位数，然后加和。这样的数一定会构成m^n个。输出最小的n个即可。

解题思路：

   思路： 因为，要每行都取一个，构成一个和sum。需要找出n个sum。  我们需要一行一行的找，不妨先设前两行的最小的n个sum是由第一行n个数和第二行的第一个数构成的。 存入c[]数组里，然后一次遍历第二行其他的数，看是否有小于c[]数组里最大的数，然后替换，这是前两行的最小的n个sum已经找到，存到了c[]数组， 然后找前三行，同样设让第三行的第一个数与数组c[]所有的数加和， 然后遍历第三行其他的数，看是否有小于c[]数组里最大的数。替换。以此类推。找到第m-1行  结束寻找，这时数组c[]里就是题目要求的数组。

    实现：因为做的是堆和优先队列，所以优先想到用优先队列实现最大堆，这样Q.top（）始终存的是n个sum中最大的那个数，而且判断，替换后，优先队列自动从大到小排列。（ps：不知道不用优先队列，每次排序会不会超时。）注意：（剪枝时注意序列的排列，代码中有说明）。

代码1：正常做法 T：4000+

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
/***************************************/
#define ll long long
#define int64 __int64
/***************************************/
const int INF = 0x7f7f7f7f;
const double eps = 1e-8;
const double PIE=acos(-1.0);
const int d1x[]= {0,-1,0,1};
const int d1y[]= {-1,0,1,0};
const int d2x[]= {0,-1,0,1};
const int d2y[]= {1,0,-1,0};
const int fx[]= {-1,-1,-1,0,0,1,1,1};
const int fy[]= {-1,0,1,-1,1,-1,0,1};
/*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/
/***************************************/
void openfile()
{
    freopen("data.in","rb",stdin);
    freopen("data.out","wb",stdout);
}
priority_queue<int> qi1;
priority_queue<int, vector<int>, greater<int> >qi2;
/**********************华丽丽的分割线,以上为模板部分*****************/
const int M=2005;
int s[M],sum[M];
int main()
{
    int cas;
    scanf("%d",&cas);
    priority_queue<int >Q;
    while(cas--)
    {
        int m,n;
        scanf("%d%d",&m,&n);
        int i,j,k;
        while(!Q.empty())
            Q.pop();
        for(i=0; i<n; i++)
            scanf("%d",&s[i]);
        for(i=1; i<m; i++)
        {
            for(j=0; j<n; j++)
            {
                scanf("%d",&sum[j]);
            }
            for(j=0; j<n; j++)
                Q.push(sum[0]+s[j]);
            int max;
            for(j=1; j<n; j++)
                for(k=0; k<n; k++)
                {
                    max=sum[j]+s[k];
                    if (max<Q.top())
                    {
                        Q.pop();
                        Q.push(max);
                    }
                }
            int d=0;
            while(!Q.empty())
            {
                s[d++]=Q.top();
                Q.pop();
            }
        }
        sort(s,s+n);
        printf("%d",s[0]);
        for(i=1; i<n; i++)
            printf(" %d",s[i]);
        printf("
");
    }
    return 0;
}

代码2：剪枝  T：800+（估计是数据的原因）

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
/***************************************/
#define ll long long
#define int64 __int64
/***************************************/
const int INF = 0x7f7f7f7f;
const double eps = 1e-8;
const double PIE=acos(-1.0);
const int d1x[]= {0,-1,0,1};
const int d1y[]= {-1,0,1,0};
const int d2x[]= {0,-1,0,1};
const int d2y[]= {1,0,-1,0};
const int fx[]= {-1,-1,-1,0,0,1,1,1};
const int fy[]= {-1,0,1,-1,1,-1,0,1};
/*vector <int>map[N];map[a].push_back(b);int len=map[v].size();*/
/***************************************/
void openfile()
{
    freopen("data.in","rb",stdin);
    freopen("data.out","wb",stdout);
}
priority_queue<int> qi1;
priority_queue<int, vector<int>, greater<int> >qi2;
/**********************华丽丽的分割线,以上为模板部分*****************/
const int M=2005;
int s[M],sum[M];
int main()
{
    int cas;
    scanf("%d",&cas);
    priority_queue<int >Q;
    while(cas--)
    {
        int m,n;
        scanf("%d%d",&m,&n);
        int i,j,k;
        for(i=0; i<n; i++)
            scanf("%d",&s[i]);
        for(i=1; i<m; i++)
        {
            sort(s,s+n); //需要排序
            for(j=0; j<n; j++)
            {
                scanf("%d",&sum[j]);
            }
            for(j=0; j<n; j++)
                Q.push(sum[0]+s[j]);
            int max;
            for(j=1; j<n; j++)
                for(k=0; k<n; k++)
                {
                    max=sum[j]+s[k];
                    if (max>=Q.top())  //因为这个地方需要使后面的数都保证大于Q.POP(),所以需要对s数组排序。
                        break;
                    if (max<Q.top())
                    {
                        Q.pop();
                        Q.push(max);
                    }
                }
            int d=0;
            while(!Q.empty())
            {
                s[d++]=Q.top();
                Q.pop();
            }
        }
        sort(s,s+n);
        printf("%d",s[0]);
        for(i=1; i<n; i++)
            printf(" %d",s[i]);
        printf("
");
        while(!Q.empty())
            Q.pop();
    }
    return 0;
}