2018寒假集训day1

I.素数

先用筛法求素数,然后再暴力枚举就可以了。

II.晨练

小 Y 打算通过锻炼来培养自己的运动细胞,他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。
在每分钟的开始,小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地,如果小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。     
求小 Y 最多能跑多少米。

对于n<=50的数据,可以用爆搜拿30分(虽然我只打了20分)。

对于100%的数据,那一看就是dp了,题解如下:

用f[i][j]表示在第i分钟疲劳度为j时能跑的最大距离,而小Y在每一分钟都有两种选择(准确来说是三种),跑或休息,当然在疲劳度为0时也可以休息,于是便推出以下三个方程:

①f[i][0]=max(f[i][0],f[i-1][0]);(表示疲劳度为0时休息)

②f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);(表示跑)

③f[i+j][0]=max(f[i+j][0],f[i][j]);(表示休息)

最后输出f[n][0]即可。

III.奇怪的桌子

动规+组合数学?不懂。

IV.学校

最短路径问题,30%可以用SPFA,100%算法依旧不懂。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注