题目名称
拯救大兵雷诺
题目描述
新晋的星灵大主教Artanis在目睹了挚友Zeratul的牺牲之后决心对抗黑暗之神Amon。为此，他首先要团结全星区所有种族的力量。
坚定的盟友雷诺和他刚刚结束了Arcturus统治的Terran帝国正在遭受Amon控制的异虫的攻击，帮助他们即可在日后对抗Amon的时候获得帮助。
当星灵部队抵达时，人类的战线已经崩溃，Artanis预测，如果没有星灵的帮助，人类部队将在n单位时间之后彻底战败。异虫部队在战场上建立了m个据点，编号从1到m，要想帮助人类取得胜利，必须击破全部的m个据点。Artanis还预测出了击破第i个据点所需的时间Ti，同时，击破第i个据点会导致异虫的攻势减弱，人类战败的倒计时会增加Ci单位时间。此外，Artanis还计算出了星灵部队战场上任意两点间移动所需的时间Ai,j表示从第i个据点到第j个据点所需的单位时间，0 <= i, j <= m，0表示星灵部队的大本营。
由于Artanis作为大主教还是个新人，指挥能力还不足以发动多线作战，因此他只能从大本营出发，一个一个地摧毁异虫的据点。他现在想知道，在保证人类部队不全军覆没的前提下，有多少种不同的进攻顺序？
输入格式
输入包括m + 4行：
第1行包括2个整数：n和m
第2行包括m个整数：Ti
第3行包括m个整数：Ci
第4至m+4行（共m+1行）是一个(m+1) * (m+1)整数矩阵：Ai,j
整数之间使用空格分隔
输出格式
输出只包含1个整数，即不同的进攻顺序方案数
输出结尾应有一个换行符
数据规模：
0 < n <= 10000, 0 < m <= 10, 0 < Ti, Ci, Ai,j <= 1000
此外，由于星灵拥有诸多人类无法理解的高端技术，因此在据点之间移动所需的时间Ai,j不一定满足三角形不等式，即不保证满足Ai,j <= Ai,k + Ak,j，也不能保证Ai,j = Aj,i，但是Ai,i一定为0
样例输入：
5 3
1 2 3
3 2 1
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
样例输出：
2
样例解释：
只有1 2 3和2 1 3的进攻顺序才能保证倒计时始终在0以上
如果按照1 3 2的顺序来进攻的话，进攻1需要1+1 = 2的时间，还剩下3，又增加3变成6；接下来进攻3需要1+3=4的时间，还剩下2，又增加1变成3；最后进攻2需要1+2=3的时间，倒计时变成0，人类战败。
题目难度
0
题目解释
即求遍历所有m个点且不被打败的方案数，每一次能够到下一个点前提条件是该点没有被遍历过，同时目前剩余时间能够到达这一个点并且打败这一个点。
方法&解释
利用深搜回溯，第一次进入是第一个点0，当前的剩余的时间n，和当前经过的点数tot，先判断是否tot==m，如果tot达到m则说明此方案遍历了m个点，方案数++，回退到前一个点（前一个点继续循环改变后一个点），如果tot！=m则列举当前能够走的点1-m均可以作为下一个到达的点，只需要判断即可，如果b数组用来标记该点是否被走过，走过则标记为1如果没有走过则为0，判断是否走过，目前的方案没有走过该点则可以走，另一个判断是否能够在剩余时间内打败该点，如果两个条件均满足则能够走该点，于是走该点，b[j]标记为1，走的点数加一，tot++，继续往下走，进入子程序（那么j即为进入的点，时间也应该为开始的时间-a[i][j]-t[j]+c[j]）；
每一次走每一步都可以在1-m之中选择，即下面的循环，当一个方案出了之后，回退到之前的（可以以栈来模拟演示一下）子程序，回溯即b[j]标记为0，tot--相当于将该步骤走的该点置为没有走过，其实这个方法和m*m层循环并没有什么区别，都是把全部的方案都遍历，只是在之前就判断了一点是否可以进入，而不是像循环一样全部都傻傻地进行了，而且其实循环还要每一层层判断比这个难写，每一次改变方案数都是从后向前，先是最后一个点改变，所有改变完之后，然后倒数第二个点改变，接着又进入最后一步，又最后一个点改变...大致循环过程是和循环一样的，可以按照循环的改变来理解。
我的代码
1 #include<stdio.h>
2 int m, b[12] = {0}, a[12][12] = {0}, t[12] = {0}, c[12] = {0}, num = 0;
3 void does(int i, int n, int tot) {
4 int j;
5 if (tot == m) {//是否完成一个方案
6 num++;
7 return;//完成一个方案则返回
8 }
9 for (j = 1; j <= m; j++) {
10 if (b[j] == 0 && a[i][j] + t[j] < n) {//判断你目前要走的点是否可以走
11 b[j] = 1;
12 tot++;
13 does(j, n - a[i][j] - t[j] + c[j], tot);//走下一个点
14 b[j] = 0;//回溯
15 tot--;
16 }
17 }
18 }
19 int main() {
20 int n, i, j;
21 scanf("%d%d", &n, &m);
22 for (i = 1; i <= m; i++) {
23 scanf("%d", &t[i]);
24 }
25 for (i = 1; i <= m; i++) {
26 scanf("%d", &c[i]);
27 }
28 for (i = 0; i <= m; i++) {
29 for (j = 0; j <= m; j++) {
30 scanf("%d", &a[i][j]);
31 }
32 }
33 b[0] = 1;
34 does(0, n, 0);//从零点出发
35 printf("%d\n", num);
36 }
标程代码
1 #include <stdio.h>
2
3 #define MAXm 11
4
5 typedef struct {
6 int x, i, n;
7 } str;
8
9 int main() {
10 int m, i, j, t = 0, ans = 0;
11 char visited[MAXm] = { 0 };
12 str stack[MAXm];
13 int A[MAXm][MAXm], T[MAXm], C[MAXm];
14 scanf("%d%d", &stack[0].n, &m);
15 for (i = 1; i <= m; ++i)
16 scanf("%d", T + i);
17 for (i = 1; i <= m; ++i)
18 scanf("%d", C + i);
19 for (i = 0; i <= m; ++i)
20 for (j = 0; j <= m; ++j)
21 scanf("%d", &A[i][j]);
22 stack[0].x = 0;
23 stack[0].i = 0;
24 while (t >= 0) {
25 if (t == m) {
26 ++ans;
27 visited[stack[t].x] = 0;
28 --t;
29 } else {
30 while (++stack[t].i <= m)
31 if (A[stack[t].x][stack[t].i] + T[stack[t].i] < stack[t].n
32 && !visited[stack[t].i]) {
33 stack[t+1].i = 0;
34 stack[t+1].x = stack[t].i;
35 stack[t+1].n = stack[t].n - A[stack[t].x][stack[t].i]
36 - T[stack[t].i] + C[stack[t].i];
37 visited[stack[t++].i] = 1;
38 break;
39 }
40 if (stack[t].i > m)
41 visited[stack[t--].x] = 0;
42 }
43 }
44 printf("%d\n", ans);
45 return 0;
46 }
标答解释
第一次写题解，希望以后可以坚持写下去，写的不好，大家见谅~