#include#include#include#include#include

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

ural Timus 1303. Minimal Coverage

系統 2183 0

http://acm.timus.ru/problem.aspx?space=1&num=1303

簡單dp ?排序枚舉就可以 不過由于M最多可以是5000

所以需要用到一定的優化 ?

比如說 ?既然要覆蓋 0---m 那么在0左邊的區間 和在m右邊 的區間 ?和被其他區間包含的區間 ?都應該去掉

代碼:

      #include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<queue>

#include<stack>

#include<cmath>

#define LL long long



using namespace std;

const int N=100005;

const int INF=0x6fffffff;

struct node

{

    int x,y;

}mem[N];

int f[N];

int sum[N];

int ans[N];

bool cmp(node a,node b)

{

    if(a.x==b.x)

    return a.y>b.y;

    return a.x<b.x;

}

void Fans(int l,int n)

{

    for(int i=n;i>=1;--i)

    {

        ans[i]=l;

        l=f[l];

    }

}

int main()

{

    //freopen("data","r",stdin);

    int m;

    int x,y;

    scanf("%d",&m);

    int I=0;

    while(scanf("%d %d",&x,&y))

    {

        if(x==0&&y==0)

        break;

        if((x>=m&&y<=0)||(x==y))

        continue;

        mem[I].x=x;mem[I].y=y;++I;

    }

    sort(mem,mem+I,cmp);

    memset(sum,-1,sizeof(sum));

    int k=-1;

    if(mem[0].x>0)

    {

         printf("No solution\n");return 0;

    }

    int n=I;

    I=0;

    for(int i=0;i<n;++i)

    {

        int l=0;

        if(i>0&&mem[i].x!=mem[I-1].x)

        for(l=0;l<I;++l)

        {

            if(mem[l].x<=mem[i].x&&mem[i].y<=mem[l].y)

            break;

        }

        if(l==I)

        {mem[I].x=mem[i].x;mem[I].y=mem[i].y;++I;}

    }

    for(int i=0;i<I;++i)

    {

        int x=mem[i].x;

        int y=mem[i].y;

        if(i>0&&x==mem[i-1].x)

        continue;

        if(x<=0)

        {

            sum[i]=1;

            f[i]=-1;

            if(y>=m&&(k==-1||sum[i]<sum[k]))

            {

                k=i;

            }

        }else

        {

            int temp=INF;int l=-1;

            for(int j=0;j<i;++j)

            {

                if(sum[j]!=-1&&mem[j].y>=x&&sum[j]<temp)

                {

                    temp=sum[j];l=j;

                }

            }

            if(l!=-1)

            {

                sum[i]=sum[l]+1;

                f[i]=l;

                if(y>=m&&(k==-1||sum[i]<sum[k]))

                {

                    k=i;

                }

            }

        }

    }

    if(k==-1)

    printf("No solution\n");

    else

    {

        printf("%d\n",sum[k]);

        Fans(k,sum[k]);

        for(int i=1;i<=sum[k];++i)

        {

            printf("%d %d\n",mem[ans[i]].x,mem[ans[i]].y);

        }

    }

    return 0;

}


    

ural Timus 1303. Minimal Coverage


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 不卡一区二区在线 | 香蕉人精品视频多人免费永久视频 | 玖玖精品在线观看 | 日本不卡一区二区三区视频 | 国产成人精品一区二区视频 | 日韩中文字幕在线有码视频网 | 色综合激情网 | 亚洲午夜久久久久国产 | 九九九精品视频免费 | 精品国产区一区二区三区在线观看 | 色婷婷基地 | 综综综综合网 | 亚洲精品久久久久久久久久ty | 最近免费中文字幕大全免费版视频 | 久久手机精品视频 | 精品一区二区在线欧美日韩 | 豆国产97在线 | 中国 | 亚洲国产精品一区二区不卡 | 一区二区三区免费在线 | 久热综合 | 免费看成人频视在线视频 | 国产精品99re| 日本三级日本三级人妇三级四 | 中文字幕天堂久久精品 | 久久黄色免费视频 | 日本一级α一片免费视频 | 亚洲精品香蕉一区二区在线观看 | 婷婷sese| 国产高清视频在线免费观看 | 国产又黄又a又潮娇喘视频 国产又色又爽又黄又刺激18 | 中国美女一级毛片 | 日日操天天操夜夜操 | 欧美人牲囗毛片 | 全部免费特黄特色大片中国 | 亚洲精品视频二区 | 婷婷综合亚洲 | 成 人 黄 色视频免费播放 | 日本在线观看不卡免费视频 | 免费看黄色的视频 | 亚洲精品中文字幕第一区 | 国产不卡在线观看视频 |