JZOJ[8.15比赛]题解

第一题：icow

刚看这题的时候觉得要用快排，但其实不用。我们只须将每次经过题目要求改变的r数组中的最大值输出即可，并按照题目要求改变r数组。

第二题：化妆晚会

我们可以用头尾指针来做这道题。首先将大于s的l[i] 赋值为0，再将l数组中没有为0的值按照从小到大快排一下，再用while循环枚举头尾指针，求出ans。

第三题：奶牛的比赛

这题我们只要用getfather和getson来求出与i直接或间接比过赛的牛，如果getfather(i)+getson(i)的值是等于n-1，我们就可累加ans。

第四题：贝茜的晨练计划

这题我们需要用到动态规划，设f[i,j]表示第i分钟贝茜疲劳度为j的路程最大值，我们可以发现有两种情况：

（1）休息：f[i,j]:=max(f[i,0],f[i-j,j]);f[i,0]:=f[i,j];

（2）走路：f[i,j]:=max(f[i-1,j-1],f[i,j]);