【2018寒假】2-8

By shy

辛(qi)亥(mo)革(kao)命(shi)刚刚结束,就要复(han)辟(jia)帝(ji)制(xun)了。

废话不说了,开讲。

然而还是照例要废话几句的

今天懒得废话了,还是讲吧。

1,素数

题目描述

有一些正整数能够表示为一个或连续多个素数的和。那么给定一些正整数,求有多少种这样的表示。对于100%的数据,所有数<=32767。

Solve

首先,枚举每个数所有的和的表示,然后判断是不是素数是一种方法,但是复杂度太高,得想另一个办法。
很明显的我们可以先用埃氏筛(是的我就是不会线性筛)筛出32767以内的素数,然后注意到题目:一个或连续多个素数的和。这样我们可以直接暴力枚举每一个素数作为起点,每次用原数减去相邻的素数直到原数不大于0。当原数=0时,方案数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*计算方案数*/
//pr[]为筛出的素数(有序排列)
int dfs(int a)
{
    int sum=0;//方案数
    for(int i=1;i<=t&&pr[i]<=a;i++)//枚举素数"起点"
    {
        int j=i,f=a;
        while(f-pr[j]>=0)//不断减去相邻的素数直到原数不大于0
        {
            f-=pr[j];
            ++j;
        }
        if(f==0) ++sum;
    }
    return sum;
}

2,贝茜的 晨练 计划

题目描述

奶牛们小 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 最多能跑多少米。

Thinking

看到这题就知道是个DP。接着我们要推方程。

首先,用f[i][j]表示在第i分钟j点疲劳度的跑步最远路程。

第i分钟疲劳度为0的最优解是上一分钟疲劳度为1和0中的最优解,于是有:

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

紧接着,第i分钟疲劳度为j的最优解可以由第i-1分钟疲劳度为j+1的最优解(休息),j-1的最优解+第i分钟跑步的路程(跑步),于是有:

f[i][j]=max(f[i-1][j+1],f[i-1][j-1]+d[i]);

然后就愉快的炸掉了。

Solve

还好我的辛苦没有白费,至少理解正解时轻松了许多。继续为自己的错误赋予意义。

还是用f[i][j]表示在第i分钟j点疲劳度的跑步最远路程(最优解)。

方程如下:

f[i][0] = max(f[i][0],f[i-1][0])。//第i分钟疲劳度为0的最优解可以通过第i-1分钟疲劳度为0的最优解转化。

f[i][j] = max(f[i][j],f[i-1][j-1] + d[i])。//第i分钟疲劳度为j的最优解可以通过第i-1分钟疲劳度为j-1的最优解+第i分钟跑步的路程d[i]转化。

f[i+j][0] = max(f[i+j][0],f[i][j])。//这一条是最重要的,因为结束时疲劳度必须为0,所以是有限制的。那么因为疲劳度为j时需要休息j分钟才能成为0,所以i+j分钟时疲劳度j为0,(目前的)最优值为第i分钟疲劳度为j时的最优值。

链接:

7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

发表评论

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