现在的位置: 首页 > 算法 > 正文

poj 1769 Minimizing maximizer(线段树&dp)

2019年04月13日 算法 ⁄ 共 3101字 ⁄ 字号 评论关闭
Minimizing maximizer
Time Limit: 5000MS   Memory Limit: 30000K
Total Submissions: 3118   Accepted: 1224

Description

The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs. 

Maximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The
n-th output of the last sorter is the output of the Maximizer. 

An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing
correct results for all possible combinations of input values? 

Task 
Write a program that: 

reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline, 
computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data, 
writes the result. 

Input

The first line of the input contains two integers n and m (2 <= n <= 50000, 1 <= m <= 500000) separated by a single space. Integer n is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described
in the next m lines. The k-th of these lines contains the parameters of the k-th sorter: two integers ik and jk (1 <= ik < jk <= n) separated by a single space.

Output

The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data.

Sample Input

40 6
20 30
1 10
10 20
20 30
15 25
30 40

Sample Output

4

Hint

Huge input data, scanf is recommended.

Source

题意

题意不是很好懂。说依次给你m个区间[li,ri]。要你依次。注意是依次不能打乱顺序。选一些区间将[1,n]覆盖。问需要的最少区间数。

思路:

dp[i]表示覆盖[1,i]需要的最少区间数。然后用线段树更新取最小值。

详细见代码:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=50010;
typedef __int64 ll;
int minv[maxn<<2],dp[maxn];
void btree(int L,int R,int k)
{
    int ls,rs,mid;
    minv[k]=INF;
    if(L==R)
        return;
    ls=k<<1;
    rs=ls|1;
    mid=(L+R)>>1;
    btree(L,mid,ls);
    btree(mid+1,R,rs);
}
void update(int L,int R,int k,int p,int v)
{
    int ls,rs,mid;

    if(L==R)
    {
        minv[k]=v;
        return;
    }
    ls=k<<1;
    rs=ls|1;
    mid=(L+R)>>1;
    if(p>mid)
        update(mid+1,R,rs,p,v);
    else
        update(L,mid,ls,p,v);
    minv[k]=min(minv[ls],minv[rs]);
}
int qu(int L,int R,int l,int r,int k)
{
    int ls,rs,mid;

    if(l==L&&r==R)
        return minv[k];
    ls=k<<1;
    rs=ls|1;
    mid=(L+R)>>1;
    if(l>mid)
        return qu(mid+1,R,l,r,rs);
    else if(r<=mid)
        return qu(L,mid,l,r,ls);
    else
        return min(qu(L,mid,l,mid,ls),qu(mid+1,R,mid+1,r,rs));
}
int main()
{
    int n,m,i,le,ri,t;

    while(~scanf("%d%d",&n,&m))
    {
        btree(1,n,1);
        memset(dp,0x3f,sizeof dp);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&le,&ri);
            if(le==1)//必须从1开始
            {
                dp[1]=dp[ri]=1;
                update(1,n,1,ri,1);
            }
            else
            {
                t=qu(1,n,le,ri,1);//查找覆盖终点范围为[le,ri]需要的最少区间。这样才能连起来并且能保证区间最少。
                if(t+1<dp[ri])
                {
                    dp[ri]=t+1;
                    update(1,n,1,ri,dp[ri]);
                }
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

抱歉!评论已关闭.