首页 > 代码库 > URAL 1203 Scientific Conference（贪心 || DP）
URAL 1203 Scientific Conference（贪心 || DP）
Scientific Conference
之前一直在刷计算几何，邀请赛连计算几何的毛都买见着，暑假这一段时间就做多校，补多校的题目，刷一下一直薄弱的DP。多校如果有计算几何一定要干掉-。-
题意：给你N个报告会的开始时间跟结束时间，问你做多可以听几场报告会。要求报告会之间至少间隔为1。
思路：其实是个活动安排问题，可以用贪心也可以用DP，贪心写起来会比较简单一些，因为练习DP，所以又用DP写了一遍。
贪心的话就是一个很简单的活动选择问题，从结束时间入手，找每次的最优选择。
1 struct node{ 2 int b, e; 3 } N[100005]; 4 5 int cmp(node x, node y){ 6 if(x.e == y.e) 7 return x.b < y.b; 8 return x.e < y.e; 9 }10 11 int n;12 int main()13 {14 scanf("%d", &n);15 for(int i = 0; i < n; ++i){16 scanf("%d%d", &N[i].b, &N[i].e);17 }18 sort(N, N+n, cmp);19 int ans = 0;20 int t = 0;21 for(int i = 0; i < n; ++i)22 {23 if(N[i].b >= t)24 {25 ans++;26 t = N[i].e+1;27 }28 }29 printf("%d\n", ans);30 31 return 0;32 }
DP：
1 struct node{ 2 int b, e; 3 } N[100005]; 4 5 int cmp(node x, node y){ 6 if(x.e == y.e) 7 return x.b < y.b; 8 return x.e < y.e; 9 }10 11 int n;12 int dp[30005];13 int k[30005];14 int main()15 {16 scanf("%d", &n);17 int last = -1;18 for(int i = 0; i < n; ++i){19 scanf("%d%d", &N[i].b, &N[i].e);20 last = max(last, N[i].e);21 }22 sort(N, N+n, cmp);23 for(int i = 0; i < n; ++i)24 {25 dp[N[i].e] = 1; ///记录结束时间是在26 k[N[i].e] = N[i].b;///记录结束时间的活动对应的开始时间27 ///之前有排序所以选择会覆盖 会是最优的28 }29 for(int i = 1; i <= last; ++i)30 {///DP时间31 if(k[i]) ///如果当前时间点有结束的活动32 dp[i] = max(dp[i-1], dp[k[i]-1]+1);33 dp[i] = max(dp[i], dp[i-1]);///如果当前时间点没有结束的活动34 }35 printf("%d\n", dp[last]);36 37 return 0;38 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。