vlambda博客
学习文章列表

                         3.24 

  相信大家如果没怎么接触动态规划的话，见到这道题的时候应该和小编一样万脸懵逼，而这道题居然还贴上简单标签，真就把小编我不当人看呗。话不多说，开始讲题解。小编大概看了下大佬们写的，总体分两种：

第一种：使用一维数组动态规划

定义一个数组dp[max];

dp[i]表示（x1,x2,....xi)中的最长预约时间

递归的方程满足：dp[i]=max(dp[i-1],dp[i-2]+xi)

第二种：使用二维数组动态规划

这种可能比较好理解

dp[i][0]表示（x1,x2,....,xi)中不接受xi的最长预约时间

dp[i][1]表示（x1,x2,....,xi)中接受xi的最长预约时间

满足方程：

dp[i][0]=max(dp[i-1][1],dp[i-1][0]);

dp[i][1]=dp[i][0]+xi;

最后比较dp[max][0]和dp[max][1]大小即可

代码：

对于这道题，其实大家如果会使用stl中multiset等容器的话，或者就使用sort(&a[0],&a[max-1])函数也是可以做出来的，但是对于快排和并排这两种非常经典的，最好还是能手撸出来，下面就是小编比较喜欢的两个模板。