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

题目


O(k+nlogn)

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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)

用链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}