蓝桥杯刷题-dp-线性dp（守望者的逃离，摆花，线段）

[NOIP 2007 普及组] 守望者的逃离

题目描述

恶魔猎手尤迪安野心勃勃，他背叛了暗夜精灵，率领深藏在海底的娜迦族企图叛变。

守望者在与尤迪安的交锋中遭遇了围杀，被困在一个荒芜的大岛上。

为了杀死守望者，尤迪安开始对这个荒岛施咒，这座岛很快就会沉下去。到那时，岛上的所有人都会遇难。

守望者的跑步速度为 17m/s，以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术，可在 1s 内移动 60m，不过每次使用闪烁法术都会消耗魔法值 10 点。守望者的魔法值恢复的速度为 4 点每秒，只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值 M，他所在的初始位置与岛的出口之间的距离 S，岛沉没的时间 T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛，若不能逃出，则输出守望者在剩下的时间内能走的最远距离。

注意：守望者跑步、闪烁或休息活动均以秒为单位，且每次活动的持续时间为整数秒。距离的单位为米。

输入格式

输入数据共一行三个非负整数，分别表示 M，S，T。

输出格式

输出数据共两行。

第一行一个字符串 Yes 或 No，即守望者是否能逃离荒岛。

第二行包含一个整数。第一行为 Yes 时表示守望者逃离荒岛的最短时间；第一行为 No 时表示守望者能走的最远距离。

输入输出样例

输入

39 200 4

输出

No

197

分析：

利用了贪心的思想：

首先，闪烁技能花费10魔法，相当于2.5s可以移动60m，比跑步1s移动17米性价比高很多。所以第一个想法就是一直闪烁，但是毫无疑问，这样会遗漏很多情况：

-1：比如上面的样例，因为跑不出去我们需要得到一个最远的距离，但是我们只知道闪烁的话，就会闪烁3次后，在最后1s还在原地不动回蓝，导致我们的最后的距离是180，毫无疑问，最后1s我们需要跑步的，而不是在原地等待，回蓝。

-2：比如下面的样例：
蓝：20 ，距离：121 时间：5

如果我们只知道使用闪烁，那么我们跑动的距离就是 60-120-120-120-180，我们会在最后1s到达，但是这哦肯定不是最优解，因为在第3s我们可以跑步就能到达终点。所以单纯的贪心不行

现在，我们假设有两个人同时在跑，有一个人很执着，他只知道使用闪烁。另外一个人是一个能时间回溯的人，他可以回到前几秒的时间，但是他一般来说只会向前跑，但是当他被第一个人超过之后，他就会回溯到前1s，学习第一个人的选择，进行闪烁，下面我们就用样例举一个例子：

代码：

#include<bits/stdc++.h>

using namespace std;

int m,s,t,first,second;

int main(){

        cin>>m>>s>>t;

        for(int i=1;i<=t;i++){

              if(m>=10)m-=10,first+=60,second+=17;//能闪烁直接闪烁

              else{  //不能闪烁

                            if(first>second)second=first;

                            m+=4,second+=17;//如果第一个人更快，第二个人学习第一个人，然后再跑       

                    }

               if(max(first,second)>=s){     //如果能到，就输出到了            

                      printf("Yes\n%d\n",i);return 0;

               }

        }

        cout<<"No"<<endl<<max(first,second)<<endl;//到不了输出距离

        return 0;

}

[NOIP 2012 普及组] 摆花

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第 i 种花不能超过 ai​ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数 n 和 m，中间用一个空格隔开。

第二行有 n 个整数，每两个整数之间用一个空格隔开，依次表示 a1​,a2​,⋯,an​。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 106+7 取模的结果。

输入输出样例

输入

2 4

3 2

输出

2

分析：

这是一道简单的0-1背包问题，下面使用了前缀和来优化我们能够选择的体积，同时也是用了滚动数组，将第一维消灭掉了

代码：
 

#include <bits/stdc++.h>

using namespace std;

const int MOD=1e6+7;

const int N=110;

int f[N]={0};

int a[N]={0};

int main(){

    int n,m;

    cin>>n>>m;

    f[0]=1; //前0个花,选择0个花,方案数是1

    int pre=0; //前缀和

    for(int i=1;i<=n;i++)scanf("%d" ,&a[i]); //读入数据,每个花的数量

    for(int i=1;i<=n;i++){//前i个花

        pre+=a[i];  //前缀和 因为我们能够选到的花最多是pre个

        for(int j=min(pre,m);j>=0;j--){ //j表示选择了j盆花只能在0~min(pre,m)里,因为使用了滚动数组,

                                                        所以倒序遍历

            for(int k=1;k<=min(j,a[i]);k++){//第i种花选择k盆，因为k=0就表示f[i-1][j]因为使用了滚动数

                                                            组，所以就可以省略掉，从1开始

                f[j]=(f[j]+f[j-k])%MOD;

            }

        }

    }

    cout<<f[m];

}

[TJOI2007] 线段

题目描述

在一个 n×n 的平面上，在每一行中有一条线段，第 i 行的线段的左端点是(i,Li​)，右端点是(i,Ri​)。

你从 (1,1) 点出发，要求沿途走过所有的线段，最终到达 (n,n) 点，且所走的路程长度要尽量短。

更具体一些说，你在任何时候只能选择向下走一步（行数增加 1）、向左走一步（列数减少 1）或是向右走一步（列数增加 1）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

输入格式

第一行有一个整数 n。

以下 n 行，在第 i 行（总第 (i+1) 行）的两个整数表示 Li​ 和 Ri​。

输出格式

仅包含一个整数，你选择的最短路程的长度。

输入输出样例

输入

6

2 6

3 4

1 3

1 2

3 6

4 5

输出

24

分析：

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=20010;

int n;int a[N][2];

int f[N][2]={0};

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

        scanf("%d%d",&a[i][0],&a[i][1]);

    }

    a[0][0]=a[0][1]=1;

for(int i=1;i<=n;i++){

        //转移到左边

        f[i][0]=1+a[i][1]-a[i][0]+min(f[i-1][0]+abs(a[i][1]-a[i-1][0]),f[i-1][1]+abs(a[i][1]-a[i-1][1]));

        //转移到右边

        f[i][1]=1+a[i][1]-a[i][0]+min(f[i-1][0]+abs(a[i][0]-a[i-1][0]),f[i-1][1]+abs(a[i][0]-a[i-1][1]));

    }

    int ans=min(f[n][0]+abs(n-a[n][0]),f[n][1]+abs(n-a[n][1]));

    cout<<ans-1; //因为第1层是从1.1转移来的，多加了一个1

    return 0;

}