http://172.20.6.3/Problem_Show.asp?id=1537
用的方法叫作浮水法,实质是递归自下而上判断一个区间有没有覆盖,O(n^2)感觉也没有很实用。
前几年的haoi怎么这么水啊。。。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,m;
int a[maxn]={},b[maxn]={};
int vis[maxn]={};
int doit(int l,int r,int x){
if(r<l)return ;
if(x==m+){
return ;
}
if(l>b[x]||r<a[x])return doit(l,r,x+);
if(l>=a[x]&&r<=b[x])return ;
if(b[x]<r&&a[x]>l)return doit(l,a[x]-,x+)|doit(b[x]+,r,x+);
if(b[x]<r)return doit(b[x]+,r,x+);
else return doit(l,a[x]-,x+);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d",&a[i],&b[i]);
}int cnt=;
for(int i=m-;i>=;i--){
if(doit(a[i],b[i],i+)){
cnt++;
}
}
printf("%d\n",cnt);
return ;
}