UVa 12018 Juice Extractor

问题描述

Jerry \texttt{Jerry}Jerry在玩水果忍者游戏，他有一个特殊能力：可以在任意时刻切割屏幕上所有的水果。每次切割时，如果切割的水果数量超过2 22个，他就能获得等同于切割水果数量的分数。每个水果有出现时间X i X_iXi​和消失时间Y i Y_iYi​，Jerry \texttt{Jerry}Jerry只能在[ X i , Y i ] [X_i, Y_i][Xi​,Yi​]时间段内切割该水果。每个水果被切割后就会消失，不能再被切割。给定N NN个水果的时间区间，求Jerry \texttt{Jerry}Jerry能获得的最大分数。

数据范围：1 ≤ N ≤ 1000 1 \leq N \leq 10001≤N≤1000，0 ≤ X i ≤ Y i ≤ 1 0 9 0 \leq X_i \leq Y_i \leq 10^90≤Xi​≤Yi​≤109。

解题思路

关键观察

1. 切割决策点：由于Jerry \texttt{Jerry}Jerry切割时会切掉屏幕上所有水果，我们需要选择一些时间点进行切割。一个重要的优化是：存在一个最优解，其中所有切割时间点都是某个水果的出现时间。

2. 排序与连续性：将水果按出现时间排序后，如果我们在某个时间点t tt切割，那么被切割的水果在排序后的数组中一定是连续的一段。

正确性证明

引理 1 ：切割时间点可以限定为水果的出现时间

证明：假设在最优解中存在一个切割时间t tt，它不是一个水果的出现时间。设这次切割覆盖的水果集合为S SS。令t ′ = max ⁡ { X i ∣ i ∈ S } t' = \max\{X_i \mid i \in S\}t′=max{Xi​∣i∈S}，即S SS中水果最晚的出现时间。由于所有i ∈ S i \in Si∈S都满足X i ≤ t ≤ Y i X_i \leq t \leq Y_iXi​≤t≤Yi​，且t ′ ≤ t t' \leq tt′≤t，所以对于任意i ∈ S i \in Si∈S，仍有X i ≤ t ′ ≤ Y i X_i \leq t' \leq Y_iXi​≤t′≤Yi​。因此，将切割时间从t tt提前到t ′ t't′不会减少被切割的水果数量，且t ′ t't′是某个水果的出现时间。由此，所有切割时间都可以调整为水果的出现时间。

引理 2 ：被切割的水果在排序后连续

证明：将水果按出现时间升序排序，设排序后的数组为a 1 , a 2 , … , a n a_1, a_2, \ldots, a_na1​,a2​,…,an​。假设在时间t tt切割，且t tt是某个水果a k a_kak​的出现时间。设被切割的水果集合为S SS。对于任意i , j ∈ S i, j \in Si,j∈S且i < j i < ji<j，假设存在m mm满足i < m < j i < m < ji<m<j但m ∉ S m \notin Sm∈/S。由于a m a_mam​的出现时间X m ≤ X j ≤ t X_m \leq X_j \leq tXm​≤Xj​≤t（因为排序后X m ≤ X j X_m \leq X_jXm​≤Xj​），且a m a_mam​没有被切割，说明Y m < t Y_m < tYm​<t。但a i a_iai​被切割意味着Y i ≥ t Y_i \geq tYi​≥t，而X m ≤ X j ≤ t X_m \leq X_j \leq tXm​≤Xj​≤t且Y m < t Y_m < tYm​<t，与排序性质矛盾。因此，S SS在排序数组中必须是连续的一段。

动态规划设计

基于以上观察，我们设计动态规划算法：

• 状态定义：令d p [ i ] dp[i]dp[i]表示考虑前i + 1 i+1i+1个水果（下标从0 00开始）时能获得的最大分数。
• 状态转移：
  1. 不切割第i ii个水果的出现时间：d p [ i ] = d p [ i − 1 ] dp[i] = dp[i-1]dp[i]=dp[i−1]。
  2. 以第i ii个水果的出现时间t = X i t = X_it=Xi​进行切割：从i ii往前遍历，统计在时间t tt仍然存在（即Y j ≥ t Y_j \geq tYj​≥t）的水果数量c n t cntcnt。如果c n t > 2 cnt > 2cnt>2，则可以从d p [ j − 1 ] dp[j-1]dp[j−1]转移，其中j jj是这组连续水果的起始下标：d p [ i ] = max ⁡ ( d p [ i ] , d p [ j − 1 ] + c n t ) dp[i] = \max(dp[i], dp[j-1] + cnt)dp[i]=max(dp[i],dp[j−1]+cnt)。
• 边界条件：d p [ − 1 ] = 0 dp[-1] = 0dp[−1]=0（没有水果时分数为0 00）。
• 最终答案：d p [ n − 1 ] dp[n-1]dp[n−1]。

复杂度分析

• 时间复杂度：O ( N 2 ) O(N^2)O(N2)，对于每个水果i ii，需要向前遍历统计可切割的水果数量。N ≤ 1000 N \leq 1000N≤1000，因此总计算量在可接受范围内。
• 空间复杂度：O ( N ) O(N)O(N)，用于存储d p dpdp数组和水果数据。

代码实现

// Juice Extractor// UVa ID: 12018// Verdict: Accepted// Submission Date: 2025-12-20// UVa Run Time: 0.000s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1010;structFruit{intstart,end;}fruits[MAXN];intdp[MAXN],n;intdfs(intp){if(p==-1)return0;if(~dp[p])returndp[p];// 第 p 个水果的出现时间不切割intr=dfs(p-1);// 第 p 个水果的出现时间作为切割时间intcnt=0;for(inti=p;i>=0;i--){if(fruits[i].end>=fruits[p].start)cnt++;if((!i||fruits[i-1].start!=fruits[i].start)&&cnt>2)r=max(r,dfs(i-1)+cnt);}returndp[p]=r;}intmain(){intt;cin>>t;for(intcaseId=1;caseId<=t;++caseId){cin>>n;for(inti=0;i<n;i++)cin>>fruits[i].start>>fruits[i].end;sort(fruits,fruits+n,[](constFruit&a,constFruit&b){if(a.start!=b.start)returna.start<b.start;returna.end<b.end;});memset(dp,-1,sizeofdp);cout<<"Case #"<<caseId<<": "<<dfs(n-1)<<'\n';}return0;}

代码说明

1. 排序：将水果按出现时间升序排序，如果出现时间相同则按消失时间升序排序。
2. 记忆化搜索：函数dfs(p)计算前p + 1 p+1p+1个水果的最大分数，使用d p dpdp数组记忆化结果。
3. 转移细节：在统计可切割水果数量时，通过条件fruits[i - 1].start != fruits[i].start确保只在连续相同开始时间的最后一个水果处进行转移，避免重复计算。
4. 输出：按照题目要求输出每个测试用例的结果。

总结

本题的关键在于将切割时间点优化为水果的出现时间，并利用排序后的连续性简化动态规划转移。通过O ( N 2 ) O(N^2)O(N2)的动态规划，可以在规定时间内求解N ≤ 1000 N \leq 1000N≤1000的问题。代码实现简洁，记忆化搜索使状态转移更加直观。