A. steve挖矿

题目大意

一个人在一个 n×m 大小的地图的 p 点开始挖矿，单位时间只能往左、或往右、或往下挖一格，其中有一些格子有矿石，矿石被挖过就没有了，有一些格子是墙壁不能走，挖矿时走过的路能重复走，请问在 t 时间后最多能获得多少价值。

• 1 <= n,m <= 10
• 1 <= t <= 10
• 时限 1s

解题思路

这是一个只有三个方向的 dfs ，因为没有明确的终点，所以递归中止的条件设为当前使用的时间 tn 是否大于规定时间 t 。题目规定走过的路可以重复走，所以 vis 数组并不是单纯用来记录走没走过，而是用来记录走过多少次，打标记的操作则应该是 vis[x][y]++ ，在 dfs 的过程中，如果当前点 vis[x][y] 值大于 1 时，说明一定是重复走了，则不需要再把当前点的矿物价值加入总和。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;

int n, m, t, sx, sy, ans = 0;
int vis[maxn][maxn];
char mp[maxn][maxn];
int dx[3] = {0, 1, 0};
int dy[3] = {-1, 0, 1};

bool in(int x, int y)
{
    if(x >= 1 && x <= n && y >= 1 && y <= m) return true;
    else return false;
}

bool isNum(int x, int y)
{
    if(mp[x][y] >= '0' && mp[x][y] <= '9') return true;
    else return false;
}

void dfs(int tn, int x, int y, int sum)
{
    if(tn > t) {
        ans = max(ans, sum);
        return;
    }
    for(int i = 0; i < 3; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(in(nx,ny) && isNum(nx,ny)) {
            vis[nx][ny]++;
            if(vis[nx][ny] > 1) dfs(tn+1, nx, ny, sum);
            else dfs(tn+1, nx, ny, sum + mp[nx][ny] - '0');
            vis[nx][ny]--;
        }
    }
}

int main()
{
    cin >> n >> m >> t;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if(mp[i][j] == 'P') sx = i, sy = j;
        }
    }
    vis[sx][sy]++;
    dfs(1, sx, sy, 0);
    cout << ans << endl;
    return 0;
}

B. 捕捉精灵

题目大意

小明想抓精灵，精灵的血量剩下越低，越容易被捕捉，现在小明有 n 个技能，第 i 个技能的伤害为 $d_i$ ，问怎样安排出招能让精灵剩下最低血量，请输出最佳方案中精灵剩余的最低血量和小明的出招次数，如果有两种方案让精灵剩余的最低血量相同，则输出出招次数较少的方案。

• 1 <= n <= 5
• 1 <= hp <= 10000
• 1 <= di <= 10000
• 时限 1s

解题思路

使用 dfs 寻找方案，dfs 函数要把攻击次数 tot 和精灵剩余血量 hpp 当参数往下传，因为题目要求不能打死精灵，假设最小伤害是 $d_x$ ，则 dfs 的终止条件是 $d_x$ > hpp。每找到一种方案，我们都要更新一次精灵最低血量和最少攻击次数。对于这道题，我们可以先把所有的伤害值从小到大排个序，在 dfs 枚举的过程中，如果枚举到的第 i 招的伤害 $d_i$ 已经超过了剩余血量 hpp，则 i 和它之后的招数都不用再枚举（简单的剪枝）。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 25;

int hp, n, d[maxn];
int ans = INF, cnt = INF;

void dfs(int tot, int hpp)
{
    // 如果连攻击力最小的招数都不能用，则说明已经是当前方案最少血量
    if(d[1] >= hpp) {
        if(hpp < ans) {
            ans = hpp;
            cnt = tot;
        }
        else if(hpp == ans) {
            cnt = min(cnt, tot);
        }
        return;
    }
    for(int i = 1; i <= n; i++) {
        if(d[i] >= hpp) break; // d数组排过序，如果当前的伤害di比剩余血量大，则剩下的技能都不用尝试
        dfs(tot+1, hpp-d[i]);
    }
}

int main()
{
    scanf("%d%d", &hp, &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &d[i]);
    }
    sort(d+1, d+1+n);
    dfs(0, hp);
    printf("%d\n%d", ans, cnt);
    return 0;
}

C. 迷宫

题目大意

有一个由 0 和 1 组成的 n×n 迷宫，入口在左上角，出口在右上角，1 表示障碍，0 表示路，迷宫中可以往八个方向走，问从起点走到终点的方案有多少。

• n <= 5
• 时限 1s

解题思路

地图 dfs 寻找方案总数的模板题，直接做就可以了，注意找准入口和出口。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;

int n,sum=0,mp[7][4],vis[7][5];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};

void dfs(int x, int y)
{
    if(x==1&&y==n) {
        sum++;
        return;
    }
    for(int i = 0; i < 8; ++i) {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==0&&vis[nx][ny]==0) {
            vis[nx][ny]=1;
            dfs(nx,ny);
            vis[nx][ny]=0;
        }
    }
}

int main()
{
    cin>>n;
    for(int i=1; i <= n; ++i) {
        for(int j = 1;j<=n;++j) {
            cin>>mp[i][j];
        }
    }
    vis[1][6]=1;
    dfs(1,1);
    cout<<sum;
    return 0;
}

D. 素数环

题目大意

有 1 到 n 的 n 个数字，如果 n 个数字的排列能满足任意两个相邻的数字（包括头尾）之和都为素数，则这种排列称之为素数环，请输出 n 个数组成的素数环的方案，如果没有则输出 no answer。

• n <= 20
• 时限 1s

解题思路

直接 dfs 寻找方案，使用一个数组记录答案，每一层选择数字的时候，除了判断有没有选过之外，还要同时判断当前选的数跟上一层选的数字之和是否为素数，当搜索到递归终点的时候，再对比一头一尾，保证满足素数环的要求。注：此题用 cin 和 cout 可能会超时。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std; 
const int maxn = 25;

int n,flag = 0;
int vis[maxn] = {0},ans[maxn] = {0};

int isprime(int n)
{
    if(n == 1) return 0;
    for(int i = 2; i <= sqrt(n); i++)
        if(n%i == 0) return 0;
    return 1;
}

void dfs(int dep)
{
    if(dep == n)
    {
        if(isprime(ans[0]+ans[dep-1])) // 判断一头一尾
        {
            for(int i = 0; i < dep; i++)
            {
                if(i) printf(" %d", ans[i]);
                else printf("%d", ans[i]);
            }
            printf("\n");
            flag = 1;
            return;
        }
    }
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i] && isprime(i+ans[dep-1])) // 判断当前选的数和前一个选的数的和是不是素数
        {
            vis[i] = 1;
            ans[dep] = i; // 深度dep可以间接表示答案数组的下标
            dfs(dep+1);
            vis[i] = 0;
        }
    }
}

int main() 
{
    scanf("%d", &n);
    ans[0] = 1; vis[1] = 1;
    dfs(1);
    if(!flag) printf("no answer");
    return 0;
}

E. 拆分k

题目大意

把一个数 n 拆成 k 份，问能有多少种拆分方法，其中如果两种拆分方法拆出来的数字都一样，只是顺序不同，则都算同一种。

• 6 < n <= 200
• 2 < k < 6
• 时限 1s

解题思路

因为 1、1、5 和 1、5、1 这些都看作是一种，所以我们可以考虑只枚举拆分序列为单调非递减的序列去代表一整类拆分，比如使用 1、1、5 代表 1、1、5；1、5、1；5、1、1 这三个拆分，所以这题的 dfs 函数需要传三个参数：深度、上一层选的数、上一层选完后还剩下的可选择大小。每一层选择的数字，一定要大于或等于上一层选的数字，并且不超过剩余总量的一半，这样才能保证选出来的序列是单调非递减的。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;

int n,k,ans;

void dfs(int dep, int x, int rst) // 深度、上一层的数字，当前还剩的余量
{
    if(dep >= k)
    {
        ans++;
        return;
    }
    for(int i = x; i <= rst/2; i++)
    {
        dfs(dep+1, i, rst-i);
    }
}

int main() 
{
    scanf("%d%d", &n, &k);
    dfs(1,1,n);
    printf("%d", ans);
    return 0;
}

F. 全排列问题

题目大意

找出 1 到 n 的所有全排列并输出，要求按字典序输出

• 1 <= n <= 9
• 时限 1s

解题思路

dfs 模板题，不解释

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 15;

int n;
int vis[maxn]={0};
int ans[maxn];//存储搜索到的排列 

void dfs(int dep)  
{  
    if(dep==n)  //dep的作用是搜索到足够的数字就输出排列数 
    {
        for(int i=0;i<n;i++)
            printf("%d ",ans[i]);
        printf("\n"); 
        return;  
    }  
    for(int i=1;i<=n;i++)  
    {  
        if(!vis[i])  
        {  
            vis[i]=true;  //标记这个数已记录，不应再取 
            ans[dep]=i;  //取数 
            dfs(dep+1);  //搜索下一个可取的数 
            vis[i]=false;  //解除标记，状态变回可取 
        }  
    }  
}  

int main() 
{
    scanf("%d", &n);
    dfs(0);
    return 0;
}

G. 组合的输出

题目大意

从 1 到 n 的 n 个数中抽出 r 个数，问能组成多少种组合（只统计递增的选择）

• 1 < n < 21
• 1 <= r <= n
• 时限 1s

解题思路

dfs 寻找即可，除了深度 dep 之外，函数还需要把上一层选的数当作第二个参数 x 往下传，保证下一层的选择一定大于上一层。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 25;

int n,r;
int ans[15];

void dfs(int dep, int x) // 参数x用于传递上一层的选择
{
    if(dep > r)
    {
        for(int i = 1; i <= r; i++)
            printf("%d ", ans[i]);
        printf("\n");
        return;
    }
    for(int i = x; i <= n; i++)
    {
        ans[dep] = i;
        dfs(dep+1, i+1);
    }
} 

int main()
{
    scanf("%d%d", &n, &r);
    dfs(1,1);
    return 0;
}

H. 自然数拆分

题目大意

把一个正整数 n 拆分成如上图的若干条加法式子

• 1 <= n <= 30
• 时限 1s

解题思路

使用 dfs 寻找方案，因为要保证拆出来的数字序列是单调非递减的，所以每次枚举选择的数字不能超过总量的一半，否则后面就没得拆了，因为要按顺序输出，所以每拆出一个数字，就输出一次最新的方案，然后再往下搜索。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std; 
const int maxn = 35;

int n;
int a[maxn];

void dfs(int dep, int n)
{
    for(int i = 1; i <= n/2; i++) // 保证枚举的时候后者一定大于前者
    {
        if(i >= a[dep-1]) // 保证后一个值一定大于等于前一个值
        {
            a[dep] = i;
            a[dep+1] = n-i;
            // 每次拆出一个数就输出一次
            for(int j=1; j<=dep+1; j++)
            {
                if(j!=1)
                    printf("+");
                printf("%d",a[j]);
            }
            printf("\n");
            
            dfs(dep+1, n-i);
        }
    }
}

int main() 
{
    scanf("%d", &n);
    dfs(1,n);
    return 0;
}

I. 工作分配问题

题目大意

有 n 件工作要分给 n 个人，假设工作 i 分配给员工 j 要花费 $C_{ij}$ ，问怎么分配能让总花费最少

• 1 <= n <= 20
• 时限 1s

解题思路

使用二维数组存储员工和工作的费用关系，然后直接 dfs 寻找方案即可。我们可以用 dfs 的层数 dep 代表当前考虑到第几个员工，对于员工 i ，只需枚举二维数组第 i 行就可以找出当前员工做每一样工作的花费，每次寻找到一种方案（即 dep > n）就更新一次最优答案，在深搜的过程中，如果这次的安排在还没到底的时候费用就已经超过了之前存储的最优答案，则该种方案不用继续深搜下去（剪枝）。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 25;

int n, c[maxn][maxn], vis[maxn], sum = 0, ans= INF;

void dfs(int dep)
{
    if(dep > n) {
        ans = min(ans, sum);
    }
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
            vis[i] = 1;
            sum += c[dep][i];
            if(sum < ans) dfs(dep+1); // 剪枝，如果当前费用已经大于之前方案的最大费用，则没必要算下去
            sum -= c[dep][i];
            vis[i] = 0;
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> c[i][j];
        }
    }
    dfs(1);
    cout << ans;
    return 0;
}

J. 装载问题

题目大意

有 n 个集装箱要装入载重量为 c 的轮船，集装箱 i 的重量为 $W_i$ ，在不考虑集装箱体积的情况下，问能装入轮船的最大重量是多少

• n <= 40
• c <= 1000
• 时限 1s

解题思路

用 dfs 去寻找所有的方案，终止条件为层数 dep > n ，对于一件物品来说，它要么放，要么不放，因此分两种方式分别往下 dfs 即可，如果在往下搜的时候，货物总重量已经大于轮船的载重，但还没搜索到底，则该分支不用继续递归下去（剪枝）。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 45;
const int maxc = 1005;

int n, c, w[maxn], ans = 0;

void dfs(int dep, int sum)
{
    if(dep > n) { // 递归到底
        if(sum <= c) {
            ans = max(ans, sum);
            return;
        }
    }
    if(sum > c) { // 总和超过轮船数（剪枝）
        return;
    }
    // 一个物品要么选择放要么选择不放
    dfs(dep+1, sum + w[dep]);
    dfs(dep+1, sum);
}

int main()
{
    scanf("%d%d", &n, &c);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}

K. N皇后问题

题目大意

在一个 n×n 的棋盘上放 n 个皇后，让他们不能互相攻击，要求输出所有的摆放方式，每种方式按次序输出每行皇后所在的列号，如果没有方案，则输出 no solute!

• n <= 10
• 时限 1s

解题思路

可以对棋盘按行进行 dfs，函数的参数 dep 表示当前处理的行号，对于每一行，我们按列号进行枚举去尝试放皇后。第 dep 层（即第 i 行）的皇后位置的选择是否合法，我们需要对比前 dep-1 层（即前 i-1 行）的所有已放置的皇后的位置来确定，只要有一个是冲突的，则该行目前枚举到的位置不能放。搜索时找到的合法位置可以用一个一维数组 ans[] 来存储，ans[i] 存储的是第 i 行的皇后所在的列号，在递归时，每一层都记录一下 ans[dep]，到最底层时，把 ans 数组输出即可。注：当 N = 2、3 时，N皇后问题一定无解。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std; 
const int maxn = 15;

int n,okflag = 0;
int ans[maxn]; //数组的下标表示行，对应的值表示列 

void dfs(int dep)
{
    int flag;
    // dfs深度为行数 
    if(dep > n)
    {
        okflag = 1;
        for(int i = 1; i <= n; i++)
        {
            if(i==1) printf("%d", ans[i]);
            else printf(" %d", ans[i]);
        }
        printf("\n");
        return;
    }
    // 每行按列继续枚举 
    for(int i = 1; i <= n; i++)
    {
        ans[dep] = i; // 代表将第一个皇后放置在第1行第i列（或者说第n个皇后）
        flag = 1;
        for(int j = 1; j < dep; j++) // 检测 这个皇后的位置和之前的n个皇后的位置是否冲突
        {
            if(ans[j] == i || (abs(dep-j)==abs(i-ans[j])))
            {
                flag = 0;
                break;
            }
        }
        // 如果没冲突，才继续向下dfs
        if(flag) dfs(dep+1); 
    }
}

int main() 
{
    scanf("%d", &n);
    dfs(1);
    if(n == 2 || n == 3 || !okflag) printf("no solute!");
    return 0;
}

L. 滑雪

题目大意

有一个 r×c 大小的二维矩阵，矩阵每个点都有一个数值表示高度，人只能从高往低走，问在这个矩阵中，能走的最长路径是多长

• 1 <= r,c <= 100
• 时限 1s

解题思路

对于地图上的任意一个点 (i,j) 来说，在 dfs 时走到它路径不止一条，所以最长路径在搜索的过程中是会实时更新的，我们要使用记忆化搜索。开一个 dis 数组用于记忆化， dis[x][y] 表示走到点 (x,y) 的最长距离，因为题目要求只能往低处走，最后总会搜索到一个点是四个方向都比他高的（类似山谷），所以不用担心没有 vis 数组会死递归。在 dfs 的过程中，如果当前点 (x,y) 的 dis[x][y] 已经被计算过，则直接返回数组中存储的结果；如果没有计算过，则对他四个方向进行 dfs ，如果某个方向的点 (nx,ny) 的高度比当前点 (x,y) 矮，则有 dis[x][y] = max(dis[x][y], dfs(nx,ny)+1)。因为地图数据有可能会有多个山峰，并不一定是从最高的那个山峰往下走是最长的（比如样例2，从 23 出发才是最优的结果），所以要对地图的每个点都作为起点进行一次 dfs ，最后输出最大的一个结果。

测试样例

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;

int mp[maxn][maxn], dis[maxn][maxn]; // dis记录到达点(i,j)的最长路径
int r, c, ans;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dfs(int x, int y)
{
    if(dis[x][y]) {
        return dis[x][y]; // 如果到该点的最长距离已经记录过，则直接返回
    }
    dis[x][y] = 1;
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && mp[nx][ny] < mp[x][y]) {
            dis[x][y] = max(dis[x][y], dfs(nx, ny)+1); // 到达点(x,y)的最远距离，要么原本已经算了，要么可以从四周其中一个比他矮的点过来
        }
    }
    return dis[x][y];
}

int main()
{
    memset(dis, 0, sizeof(dis));
    scanf("%d%d", &r, &c);
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            scanf("%d", &mp[i][j]);
        }
    }
    ans = 0;
    for(int i = 1; i <= r; i++) {
        for(int j = 1; j <= c; j++) {
            ans = max(ans, dfs(i, j)); // 因为有可能有多个山峰和陡坡，所以要每个点都dfs，取最大
        }
    }
    printf("%d", ans);
    return 0;
}

版权属于：PCsky

本文链接：http://hyouka.club/index.php/archives/178/

转载时须注明出处及本声明