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;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
