兰州网站seo服务,企业融资流程,制作视频剪辑,咨询公司排名前十名问题描述#xff1a;一名有名的按摩师会受到源源不断的预约请求#xff0c;每个预约都可以选择接或者不接#xff0c;在每次预约服务之间要有休息时间#xff0c;因此不能接相邻的预约#xff0c;给定一个请求序列#xff0c;按摩师找到最优的预约集合(总预约时间最长)一名有名的按摩师会受到源源不断的预约请求每个预约都可以选择接或者不接在每次预约服务之间要有休息时间因此不能接相邻的预约给定一个请求序列按摩师找到最优的预约集合(总预约时间最长)返回总的分钟数
递归方法求解如果上一个选择了接则此个预约不能接如果上一个没有选择接则这个预约可以选择接或者不接两种选择使用一个参变量表征上一个是否接客并在到达最后的时候将结果保存在最大堆中最后弹出顶上的元素并使用一个sum保存之前累积的值
public void getMaxTime(int []nums,int index,int isLastChoose,int sum,PriorityQueueIntegermaxheap)
{
if(inedxnums.length)
{
maxHeap.add(sum);
return
}
if(isLastChoose)
{
getMaxTime(nums,index1,false,sum,maxHeap);
}else
{
getMaxTime(nums,index,false,sum,maxHeap);
getMaxTime(nums,index1,true,sumprices[index],maxHeap);
}
}
public int GetMaxTime(int [] nums)
{
PriorityQueueIntegermaxHeapnew PriorityQueue(Collections.reverseOrder());
getMaxTime(nums,0,false,0,maxHeap);
return maxHeap.peek();
}
动态规划求解使用dp[i][0]表征不选择该元素时的前i个元素的最大时间dp[i][1]表征选择该元素时前i个元素的最大利润
public int getMaxTime(int []nums)
{
int[][]dpnew int[nums.length][2];
dp[0][0]0;
dp[0][1]nums[0];
for(int i1;inums.length;i)
{
//若不选择当前元素则上一个元素可以选也可以不选
dp[i][0]Math.max(dp[i-1][0],dp[i-1][1]);
//若选择当前元素则上一个元素只能不选然后加入num[i]
dp[i][1]dp[i-1][0]num[i]
}
return Math.max(dp[nums.length][0],dp[nums.length][1]);}
