最短Hamilton路径

给定一张$n$个点的带权无向图，点从$0∼n−1$标号，求起点$0$到终点$n−1$的最短 Hamilton 路径。

输入格式

第一行输入整数$n$。

接下来$n$行每行$n$个整数，其中第$i$行第$j$个整数表示点$i$到$j$的距离（记为$a[i,j]$）。

对于任意的$x,y,z$，数据保证$a[x,x]=0$，$a[x,y]=a[y,x]$ 并且$a[x,y]+a[y,z]≥a[x,z]$。

输出格式

输出一个整数，表示最短 Hamilton 路径的长度。

数据范围

$1≤n≤20$

$0≤a[i,j]≤10^7$

1
2
3
4
5
6
7
8
9
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18

解题思路

一道经典的旅行商 NP 问题。

一共 20 个点，共 20！种排列方式，暴力搜素肯定行不通；

观察这样两条路径：

  • 0 -> 1 -> 2 -> 3 长度为18

  • 0 -> 2 -> 1 -> 3 长度为20

显然，长度为 20 的路径肯定不是最终答案，我们不需要考虑这条路径；

因此问题转化为考虑经过了哪些点后最终到达某个点的最短 Hamilton 路径长度。

$f[i][j]$：$i$是一个二进制数，表示到达$j$点经过了哪些点，显然$i$的第$j$位保证为$1$；

$f[i][j]$可以由所有的第$j$位为$0$，第$k$位为$1$的状态$f[stk][k]$转移而来。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

typedef long long LL;

int w[N][N];

LL f[1 << N][N];

int n;

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            scanf("%d", &w[i][j]);
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;    //起点长度为0
    for(int i = 0; i < 1 << n; ++ i)
        for(int j = 0; j < n; ++ j)
            if(i >> j & 1)  // 保证合法状态
                for(int k = 0 ;k < n; ++ k)
                    if((i - (1 << j)) >> k & 1) // 合法状态
                        f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n-1];
    return 0;
}

蓝桥杯 2023 省 B 飞机降落

题目描述

$N$ 架飞机准备降落到某个只有一条跑道的机场。其中第$i$架飞机在$T[i]$时刻到达机场上空，到达时它的剩余油料还可以继续盘旋$D[i]$个单位时间，即它最早可以于$T[i]$时刻开始降落，最晩可以于$T[i] + D[i]$时刻开始降落。降落过程需要$L[i]$个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断$N架$飞机是否可以全部安全降落。

输入格式

输入包含多组数据。

第一行包含一个整数$T$，代表测试数据的组数。

对于每组数据，第一行包含一个整数$N$。

以下$N$行，每行包含三个整数$T[i],D[i],L[i]$ 。

输出格式

对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

样例输出 #1

1
2
YES
NO

提示

【样例说明】

对于第一组数据，可以安排第$3$架飞机于$0$时刻开始降落，$20$时刻完成降落。安排第$2$架飞机于$20$时刻开始降落，$30$时刻完成降落。安排第$1$架飞机于$30$时刻开始降落，$40$时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

解题思路

$f[i][j]$表示$i$中数位为$1$的飞机已经降落且最后一架降落的飞机是$j$的最小落地时间 （显然保证$i$的第$j$位为$1$）

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10, M = 1 << N;

int f[M][N];

int t[N],d[N],l[N];

int n,T;

int main() {
    cin >> T;
    while(T--) {
        scanf("%d", &n);
        for(int i = 0 ; i < n; ++ i) scanf("%d%d%d",&t[i],&d[i],&l[i]);
        memset(f, 0x3f, sizeof f);
        for(int i = 0;i < n; ++ i) f[1 << i][i] = t[i] + l[i];
        for(int i = 0; i < 1 << n; ++ i)
            for(int j = 0; j < n; ++ j)
                if(i >> j & 1)
                    for(int k = 0; k < n; ++ k)
                        if(i - (1 << j) >> k & 1 && f[i - (1 << j)][k] <= t[j] + d[j])
                            f[i][j] = min(f[i][j],max(t[j],f[i - (1 << j)][k]) + l[j]);
        int res = 0x3f3f3f3f;
        for(int j = 0; j < n; ++ j)
            res = min(f[(1 << n) - 1][j],res);
        if(res == 0x3f3f3f3f) puts("NO");
        else puts("YES");
    }
    return 0;
}

国际象棋

众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放$8$个皇后，使得两两之间互不攻击的方案数。

已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在$N \times M$的棋盘上，摆放$K$个马，使得两两之间互不攻击有多少种摆放方案。

由于方案数可能很大，只需计算答案除以$1000000007$(即$10^9+7$) 的余数。

如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 (x,y) 格的马（第 x 行第 y
列）可以攻击 $(x+1,y+2)$、$(x+1,y−2)$、$(x−1,y+2)$、$(x−1,y−2)$、$(x+2,y+1)$、$(x+2,y−1)$、$(x−2,y+1)$ 和 $(x−2,y−1)$ 共 8 个格子。

国际象棋

输入格式
输入一行包含三个正整数$N,M,K$，分别表示棋盘的行数、列数和马的个数。

输出格式
输出一个整数，表示摆放的方案数除以$1000000007$(即$10^9+7$) 的余数。

数据范围
对于 $5\%$ 的评测用例，$K=1$；对于另外 10% 的评测用例，$K=2$；
对于另外 $10\%$ 的评测用例，$N=1$；
对于另外 $20\%$ 的评测用例，$N,M≤6$，$K≤5$；
对于另外 $25\%$ 的评测用例，$N≤3，M≤20，K≤12$；
对于所有评测用例，$1≤N≤6，1≤M≤100，1≤K≤20$。

1
2
3
4
5
6
7
8
9
10
11
12
输入样例1：
1 2 1
输出样例1：
2
输入样例2：
4 4 3
输出样例2：
276
输入样例3：
3 20 12
输出样例3：
914051446

解题思路

$dp$问题的显著特征就是可以把大问题化成小问题，再化零为整；

考虑棋子的放置过程，显然如果一列一列的放置棋子，显然棋子的放置只会受到前两列的影响（同一列棋子显然不会发生冲突）；

于是我们考虑子问题：前$i$列已经放置完毕，并且第$i$列和第$i-1$列的状态分别是$a$、$b$，且已经放置了$j$枚棋子的方案数；

这时我们只需要顺序枚举每一列 $i$、$i - 1$ 列、 $i$ 列、$i - 2$列、棋子数目$j$即可；

最多循环次数$100 \times 64 \times 64 \times 64 \times 20$次;

这个数字大约是$5 \times 10^9$；

但是在枚举过程中状态之间需要保证不发生冲突，即$a$与$b$不能出现间隔$2$位为$1$的情况，
$c$与$a$同理，并且$c$与$b$不能出现间隔$1$位为$1$的情况；

此外，$j$的枚举从$b$中有的$1$的个数开始，到$k$结束；

在实际运行中，大约运算了七百多万次。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10,M = 110,mod = 1e9 + 7;

int n,m,k;

int f[M][1 << 6][1 << 6][30];

int get(int x){
    int res = 0;
    while(x) {
        ++ res;
        x -= x & -x;
    }
    return res;
}

int main() {
    cin >> n >> m >> k;
    f[0][0][0][0] = 1;
    for(int i = 1; i <= m; ++ i)
        for(int a = 0; a < 1 << n; ++ a)
            for(int b = 0; b < 1 << n; ++ b) {
                if(a & (b << 2) || b & (a << 2)) continue;
                    for(int c = 0; c < 1 << n; ++ c) {
                        if(a & (c << 2) || c & (a << 2)) continue;
                        if(c & (b << 1) || b & (c << 1)) continue;
                        int w = get(b),v = get(a);
                        for(int j = v + w; j <= k; ++ j)
                            for(int t = get(c) + v; t <= k - w; ++ t)
                                f[i][a][b][j] = (f[i][a][b][j] + f[i-1][c][a][t])
                    }
            }
    int res = 0;
    for(int a = 0; a < 1 << n; ++ a)
        for(int b = 0; b < 1 << n; ++ b)
            res  = (res + f[m][a][b][k]) % mod;
    cout << res << endl;
    return 0;
}