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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
