题目名称
拯救大兵雷诺
题目描述
新晋的星灵大主教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 ", 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 ", ans); 45 return 0; 46 }
标答解释
第一次写题解，希望以后可以坚持写下去，写的不好，大家见谅~