2.8数据结构与算法学习日记（bfs和01背包和完全背包）

P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱

题目描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 N×N 个格子组成的二维迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 . 表示；

有些格子是墙壁，小明不能经过，我们用 # 表示。

此外，有些格子上有陷阱，我们用 X 表示。除非小明处于无敌状态，否则不能经过。

有些格子上有无敌道具，我们用 % 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 K 步。

之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫。

输入格式

第一行包含两个整数 N 和 K。(1≤N≤1000，1≤K≤10)。

以下 N 行包含一个 N×N 的矩阵。

矩阵保证左上角和右下角是 .。

输出格式

一个整数表示答案。如果小明不能离开迷宫，输出 −1−1。

输入输出样例

输入 #1复制

5 3
...XX
##%#.
...#.
.###.
.....

输出 #1复制

10

输入 #2复制

5 1
...XX
##%#.
...#.
.###.
.....

输出 #2复制

12

说明/提示

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

题目分析

1，题目需考虑无敌状态以及无敌道具，所以我们需要在bfs时把这些条件加进去考虑，定义一个标记数组用来表是否走过和当前无敌所剩时间

2.在结构体内新加一个变量 magic，表示当前还剩几步的无敌状态。在遍历过程中，如果遇到“X”，并且不剩无敌了，就不能走；如果遇到“%”，magic 会重置成k。其他情况，并且不为“#”时，该点入队。

3，再进行剪枝操作符合能走的条件（book[nx][ny]<magic的作用是把肯定不是最优的情况排除，就是当前我走这个点剩下的无敌步数要大于之前剩下的，这会更优，所以可以走）

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,k;
char a[N][N];
int book[N][N];
struct node
{
    int x,y,step,magic;
};
int dx[4]= {1,-1,0,0};//方向数组
int dy[4]= {0,0,1,-1};
int bfs()
{
    queue<node>p;
    book[1][1]=0;
    p.push({1,1,0,0});
    while(p.size())
    {
        node t=p.front();//查看队列头
        p.pop();
        if(t.x==n&&t.y==n)
        {
            cout<<t.step;
            return 0;//到达终点所以输出步数然后返回
        }
        for(int i=0; i<4; i++)
        {
            int nx=t.x+dx[i];
            int ny=t.y+dy[i];
            if(a[nx][ny]=='X'&&t.magic==0)//没有无敌又有陷阱，所以不能走
                continue;
            int magic=max(0,t.magic-1);//查看现在的无敌剩下步数
            if(a[nx][ny]=='%')magic=k;
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&book[nx][ny]<magic&&a[nx][ny]!='#')//符合能走的条件（book[nx][ny]<magic的作用是把肯定不是最优的情况排除，就是当前我走这个点剩下的无敌步数要大于之前剩下的，这会更优，所以可以走）
            {
                book[nx][ny]=magic;
                p.push({nx,ny,t.step+1,magic});//入队更新步数和无敌状态
            }
 
 
 
        }
 
 
    }
    cout<<-1;
    return 0;
}
 
int main(){
 
cin>>n>>k;
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>a[i][j];
memset(book,-1,sizeof(book));//初始化为-1
bfs();
 
 
 
}
 
 
 

P1115 最大子段和

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai​。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

7
2 -4 3 -1 2 -4 3

输出 #1复制

4

说明/提示

样例 1 解释

选取 [3,5][3,5] 子段 {3,−1,2}{3,−1,2}，其和为 44。

数据规模与约定

• 对于 40%40% 的数据，保证 n≤2×103。
• 对于 100%100% 的数据，保证 1≤n≤2×105，−104≤ai​≤104。

题目分析 

1，既然是求最大的子段和，所以我们要找出每个子段的和并边找边比大小，所以有个max变量一直在存放最大值

2，记录子段和，b[i]记录到i时，i之前的所有子段和

3，对于一直往后加，我们可以这样考虑（取与不取）取的条件是要求取他后总和会比之前的大，不然取着没意义，不取是加上后还比之前的小，那么就到这吧，不取了，下一个子段的开头以他为首赋值给b[i];

代码示例

#include<bits/stdc++.h>
using namespace std;
int b[200020],a[200020],i,n,ans=-9999;//因为要取最大值，所以从最小的开始找
int main(){
       cin>>n;
       for(i=1;i<=n;i++)
        {cin>>a[i];
           if(n==1)b[i]=a[i];
     else b[i]=max(a[i],b[i-1]+a[i]);//判断取不取，哪个更优
       ans=max(ans,b[i]);//最大值
        }
        cout<<ans;
 
 
 
}

 p1616疯狂的采药

题目背景

此题为纪念 LiYuxiang 而生。

题目描述

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

1. 每种草药可以无限制地疯狂采摘。

2. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。

第 2 到第 (m+1) 行，每行两个整数，第 (i+1) 行的整数 ai​,bi​ 分别表示采摘第 i 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例

输入 #1复制

70 3
71 100
69 1
1 2

输出 #1复制

140

说明/提示

数据规模与约定

• 对于 30%30% 的数据，保证 m≤103 。
• 对于 100%100% 的数据，保证 1≤m≤104，1≤t≤107，且 1≤m×t≤107，1≤ai​,bi​≤104

 题目分析

1，和之前的采药http://t.csdnimg.cn/SFpwD不同的是，他是可以重复采摘，所以在这里就变成了完全背包问题

2，此时给他数组压缩成一维数组得到dp[j]=max(dp[i],dp[j-w[i]]+v[i])

3.j表截止到j时的最大容量，dp[j]表截止到j容量的价值

代码示例

#include<bits/stdc++.h>
using namespace std;
const int maxm=10010,maxt=10000010;
long long v[maxm],t[maxt],dp[maxt];
int main(){
    int T,m;
    cin>>T>>m;
    for(int i=1;i<=m;i++)
    cin>>t[i]>>v[i];
        for(int i=1;i<=m;i++)
        for(int j=t[i];j<=T;j++)//完全背包一维数组用从前往后遍历（这样会保证重复取），01背包一维数组从后往前遍历
        dp[j]=max(dp[j],dp[j-t[i]]+v[i]);//判断是否取，然后j表截止到j的最大容量，dp[j]表截止到j容量的价值
    cout<<dp[T];
 
 
 
 
 
}