浮尘~ 于 2019-03-20 22:11:11 发布
博客探讨了如何编写递归程序，以解决大臣J在T王国旅行时的最大花费问题。给定城市间的道路和距离，J大臣从一个城市出发到另一个城市，中间不休息，目标是找出所有可能路线中费用最高的。文章提供了输入输出格式，样例输入和输出，以及资源限制，挑战读者设计一个不超过64MB内存和5秒CPU消耗的解决方案。 递归程序如何编写：
1.确定出口（剪枝）叶子节点，数组边界，
2.确定参数（一般有每次递归会变得参数（递归层数，距离之和），此层相关的数组下标（节点标号），求解的一般是最值，可以设置为全局变量，还有权重数组，ans，vis，节点数量）
3.回溯（递归过程中，如果改变了节点的属性，需要把它改回来，例如全排列的swap两次，比如bfs可能需要考虑是否访问）
4.dfs中的for循环（或者几个dfs连在一起）的意思是想要把当前一层的所有下一层可能遍历一次
#include<iostream> #include<algorithm> using namespace std; int n; //非字典序方法一：递归确定第一个，然后确定后面n-1个全排列 //void swap(int i, int j, int a[]) { // int t = a[i]; // a[i] = a[j]; // a[j] = t; //} // //void dfs(int flag, int a[]) { // if (flag == n - 1) { // for (int i = 0; i < n; ++i) { // printf("%d",a[i]); // } // // } // for (int j = flag; j <n ; ++j) { // swap(flag,j,a); // dfs(flag+1,a); // swap(flag,j,a); // } //} // // //int main() { // scanf("%d", &n); // int a[n]; // for (int i = 0; i < n; i++) { // a[i] = i+1; // } // dfs(0, a); // return 0; //} //方法二：字典序：从右想左先找到相邻的左边比较小的（12354找到3）pi，然后从右向左Pn-1 - pi找到第一个大于pi的pj，将pi，pj交换，将pi之后的反转。 //
123456789101112131415161718192021222324252627282930313233343536373839
