POJ 1065 贪心算法(Dilworth定理)

2017年3月28日 2点热度 0条评论 来源: 林小贱_myself

[POJ 1065 传送门](http://vj.acmclub.cn/problem/viewProblem.action?

id=5354)

一.Dilworth定理

      本定理输入离散数学的知识,讲解此定理之前,首先科普一些相关知识:
      链(chain)是一个偏序集S的全序子集(所谓全序是指任意两个元素可比较)
      反链(antichain)是一个偏序集S的子      集,其中任意两个元素不可比较
      极大(maximal)链:对一个链C,如果找不到另一个链C’,使得C是C’的真子集,那么称链C是极大的
      极大(maximal)反链:对一个反链A,如果找不到另一个反链A’,使得A是A’的真子集,那么称反链A是极大的
      最大链(maximum/longest):链C包含元素个数不少于任意其他链C’,则C是最大链
      最大反链(maximum/largest):反链D包含元素的个数不少于任意其他链D’,则D是最大反链
(有上面推倒可知,最大链必然是极大链,最大反链必然是极大反链

      Dilworth定理说明,存在一个反链A与一个将序列划分为链族P的划分,使得划分中链的数量等于集合A的基数。当存在这种情况时,对任何至多能包含来自P中每一个成员一个元素的反链,A一定是此序列中的最大反链。同样地,对于任何最少包含A中的每一个元素的一个链的划分,P也一定是序列可以划分出的最小链族。偏序集的宽度被定义为A与P的共同大小。

二.思路

      由上面可知,仔细思考发现,此题是一个很典型的Dilworth定理的题目,给定了一个集合K(我们姑且这么认为),给出了length与weight这两种不同集合的关系,即p1(<=length) 与 p2(<=weight)

      不同于我们抽象理解上面定理,通俗理解,我们要对现有集合进行筛选,满足一个关系,无论是p1还是p2的关系,形成一个新的集合K’。在此基础上,我们再次求出,满足剩余的关系,无论p1还是p2。从而,找出最终的关系K”,既满足p1又满足p2,即 p1∪p2 的集合。

三.实现代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
//定义具体的元素节点
struct DataNode{
    int length;
    int weight;
};
//存放节点的数据集K
DataNode dataSet[5001];

//使用了algorithm(算法)库的qsort函数,实现快排
int cmp (const void *aa, const void *bb)
{
    struct DataNode *a = (DataNode*) aa;
    struct DataNode *b = (DataNode*) bb;
    if (a->length == b->length)
    {
        return b->weight - a->weight;
    }
    else
    {
        return  b->length - a->length;
    }
}

int main  ()
{
    int N;
    cin>>N;
    while (N--)
    {
        int data_size;
        cin>>data_size;
        for (int i=0;i<data_size;i++)
        {
            cin>>dataSet[i].length>>dataSet[i].weight;
        }
        //使用qsort函数
        qsort(dataSet,data_size,sizeof(dataSet[0]),cmp);
        //记录我们需要的时间
        int cnt_time = 0;


        //要形成一个满足<=的偏序关系,此题目的偏序关系是:weight<= && lenght<= ,需要同时满足,
        //我们可以这么认为,对于此集合s ,求出满足weight<=的偏序集 ,又求出了length<= 的偏序集,
        //对于这两个偏序集合,我们求出并集,即是满足条件的集合q

        //标记我们的数据是否满足关系(p1 或者 p2),放入集合中
        bool pd_flag[5001];
        //初始化标记数组,当时的memset()函数突然无法起作用,现在还是不明原因
        for (int i=0;i<data_size;i++)
        {
            pd_flag[i] = false;
        }
        for (int i=0;i<data_size;i++)
        {
            if (pd_flag[i] == false)//判断dataSet[i]是否已经放入某个集合中
                {
                DataNode flag_bz;
                flag_bz.length = dataSet[i].length;
                flag_bz.weight = dataSet[i].weight;
                cnt_time++;//如果还没有放入一个集合,代表此元素属于一个新的集合
                for (int j=i;j<data_size;j++)
                //筛选并标记是否在一个满足p1或者p2关系的相同集合中
                {
                    if (dataSet[j].length <= flag_bz.length && dataSet[j].weight <= flag_bz.weight && pd_flag[j] == false)
                    {
                        pd_flag[j] = true;
                        flag_bz.length = dataSet[j].length;
                        flag_bz.weight = dataSet[j].weight;
                    }
                }
            }
        }

        cout<<cnt_time<<endl;
    }
    return 0;
}
    原文作者:林小贱_myself
    原文地址: https://blog.csdn.net/ajfdlkasjgdlkas/article/details/67190175
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。