luoguP2439 [SDOI2005]阶梯教室设备利用

Date: Sun 28 October 2018
Updated: Sun 28 October 2018

In 5. OI.

Tags: OI

题目


O(k+nlogn)

f[i]表示0..i的区间的最大演讲时间。

f[i]要么不演讲从f[i-1]转移 要么演讲,从f[i-a[j].s]转移(a[j].e==i)

#include<bits/stdc++.h>
#define M 30010
#define N 10010
#define max(a,b) ((a)>(b)?(a):(b))
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
struct node{
 int s,e;
}a[N];
int f[M],n,mx;
inline int cmp(node a,node b){
 return a.e<b.e;
}
template<typename T>inline void rll(T &x){
 T f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
int main(){
 rll(n);mx=0;
 fsb(i,1,n){
  rll(a[i].s),rll(a[i].e);
  a[i].s++;a[i].e++;
 }
 sort(a+1,a+1+n,cmp);
 int j=1;mx=a[n].e;f[0]=0;
 fsb(i,1,mx){
  f[i]=f[i-1];
  while(j<=n&&a[j].e==i){
   f[i]=max(f[i],f[a[j].s]+a[j].e-a[j].s);
   j++;
  }
 }
 printf("%d\n",f[mx]);
 return 0;
}

O(n+k)

用链式前向星

#include<bits/stdc++.h>
#define M 30010
#define N 10010
#define max(a,b) ((a)>(b)?(a):(b))
#define fsb(a,b,c) for(int a=b;a<=c;a++)
#define fbs(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
struct node{
 int s,nt;
}a[N];
int f[M],n,mx,head[M],x,y;
template<typename T>inline void rll(T &x){
 T f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline void add(int x,int y,int i){
 a[i].s=y;a[i].nt=head[x];head[x]=i;
}
int main(){
 rll(n);mx=0;memset(head,255,sizeof(head));
 fsb(i,1,n){
  rll(x),rll(y);x++;y++;
  add(y,x,i);mx=max(mx,y);
 }
 f[0]=0;
 fsb(i,1,mx){
  f[i]=f[i-1];
  for(int t=head[i];t!=-1;t=a[t].nt)
   f[i]=max(f[i],f[a[t].s]+i-a[t].s);
 }
 printf("%d\n",f[mx]);
 return 0;
}

Social