请教九度1463 很简单的一个题目,不知道为什么算法好像出了问题, 谢谢
http://ac.jobdu.com/problem.php?pid=1463
#include <cstdio>
#include <string.h>
int t[25];//t[i]表示以i点结束的所有招聘会中开始最晚的,开始早的不会对能参加的活动的最大值产生更好的作用
int dp[25];//d[i]表示到i点能参加的最大招聘会个数
inline int ma(int a, int b){
return a >= b ? a : b;
}
int main(){
int n, a, b;
while(~scanf("%d", &n)){
memset(t, -1, sizeof(t));
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++){
scanf("%d%d", &a, &b);
if(t[b] < a)
t[b] = a;//b点结束的招聘会如果有更晚的开始时间,则替换原来的
}
for(int i = 1; i <= 24; i++){
if(t[i] == -1)
dp[i] = dp[i - 1];//如果这个点没有招聘会结束,说明这个到这个点能参加的最大招聘会个数跟上个点相同
else
dp[i] = ma(dp[i - 1], dp[t[i]] + 1);//如果这个点有会结束,那么比较上个点结束时最大的招聘会个数,跟t[i]点结束的招聘会个数 + 1比较,取较大值
}
printf("%d\n", dp[24]);
}
return 0;
}
