科学会议 Time Limit:1000MS  Memory Limit:16384KTotal Submit:95 Accepted:3 Description 科学会议的功能通常分为同时进行的几个分区。 例如，一个区关于并行计算，一个区关于可视化，一个区关于数据压缩，等等。 显然，若干分区的工作同时进行是必要的，以便缩减会议科学议程的时间，从而有更多的时间进行宴会，饮茶及必要的讨论。 因而，一个人感兴趣的多个报告在不同的分区同时进行是可能的。 一位与会者写出一个关于所有他感兴趣的报告的时间表。 他要求你算出他能够出席的报告的最大数目。 Input 第一行包含数字N（1 ≤ N ≤ 100000），感兴趣报告的数目。 接下来的每行包含两个整数 Ts 和 Te (1 ≤ Ts < Te ≤ 30000)，用空格分开，表示相应报告的起始和结束。 时间以距会议开始的分钟数表示。 Output 输出该与会者能够出席的报告的最大数目。 与会者不能出席两个同时进行的报告。 并且他出席的任意两个报告之间的时间间隔至少1分钟。 例如，如果他能够出席的一个报告在15分钟结束，则下一个报告必须在16分钟或更晚。 Sample Input 5 3 4 1 5 6 7 4 5 1 3 Sample Output 3 Source   校赛题目，很简单的一道DP题目，可惜比赛时没做出来，其实现在就算是AC了。我也觉得比赛时我没做错，是给的测试数据的问题。很郁闷 状态方程很简单： f[i]=max{f[i-1],f[m.x-1]+1} m.x表示i分钟结束的报告的开始时间#include<stdio.h> #include<stdlib.h> int f[30005]; struct node { int x,y; }m[100004]; int cmp( const void *a , const void *b ) { struct node *c = (node *)a; struct node *d = (node *)b; if(c->y != d->y) return c->y - d->y; else return d->x - c->x; } int main() { int N,i,k; int max=0; scanf("%d",&N); for(i=1;i<=30000;i++) f[i]=0; for(i=0;i<N;i++) { scanf("%d %d",&m[i].x,&m[i].y); if(m[i].y>max) max=m[i].y; } qsort(m,N,sizeof(m[0]),cmp); f[0]=0; k=0; for(i=1;i<=max;i++) { f[i]=f[i-1]; while(m[k].y<i) k++; if(m[k].y==i) { if(f[m[k].x-1]+1>f[i]) f[i]=f[m[k].x-1]+1; } } printf("%d\n",f[max]); return 0; }

评论