首页 > 代码库 > URAL 1203 Scientific Conference（贪心 || DP）

URAL 1203 Scientific Conference（贪心 || DP）

2024-07-13 17:05:15   213人阅读

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 }
DP


联系
我们