[140222]
0.总结：
比较顺利，比较快得做出了第一题和第二题，第三题的时候第一想法是用STL中的全排列函数(next_permutation()),后续发现改起来有点麻烦，于是就直接写回溯的全排列了。第四题对DP理解不深，用暴搜的方法能过几个点算几个点。
1.出栈顺序统计
题意：栈是常用的一种数据结构，有N个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一系列操作序列可以得到一系列的输出序列。请你编程求出对于给定的N，计算并输出由等待进栈的序列1,2，……，N，经过一系列操作可能得到的输出序列总数。(1<=n<=15)
思路：数据量不大，穷举所有的可能性。不妨假设栈中已有N个元素，现将X放入栈。其放入的顺序可以在原有栈中不弹出元素已经弹出所有元素之间
代码：
#include <iostream>#include <stack>#include <cstdio>#include <string>using namespace std;void dfs(int stack_top, int num);int n;int ans = 0;int main(){freopen("stack.in", "r", stdin);freopen("stack.out", "w", stdout);cin >> n;dfs(0, 1);cout << ans << endl;return 0;}void dfs(int stack_top, int num){if(num == n+1){ans++;return;}for(int i = 0; i <= stack_top; ++i){dfs(stack_top-i+1, num+1);}}
2.走迷宫
题意：
思路：DFS，注意回溯。学习到一个小技巧，走迷宫的时候不需要另外再设一个vis数组，直接在map数组上进行修改就好，这样可以减少操作数。另外需要注意的是把起始点设置为已访问
代码：
#include <iostream>#include <cstring>#include <cstdio>#define MAXN 15using namespace std;bool map[MAXN][MAXN];const int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};int ans = 0;int m, n;int start_x, start_y, fin_x, fin_y;void dfs(int x, int y);bool check(int x, int y);int main(){freopen("maze.in" ,"r", stdin);freopen("maze.out", "w", stdout);memset(map, false, sizeof(map));scanf("%d %d", &m, &n);int temp;for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){scanf("%d", &temp);if(temp){map[i][j] = true;}}}scanf("%d%d", &start_x, &start_y);scanf("%d%d", &fin_x, &fin_y);start_x–, start_y–, fin_x–, fin_y–;map[start_x][start_y] = false;dfs(start_x, start_y);if(ans == 0){cout << -1 << endl;}else{cout << ans << endl;}return 0;}void dfs(int x, int y){if(x == fin_x && y == fin_y){ans++;return;}for(int i = 0; i < 4; ++i){if(check(x+dir[i][0], y+dir[i][1])){map[x+dir[i][0]][y+dir[i][1]] = false;dfs(x+dir[i][0], y+dir[i][1]);map[x+dir[i][0]][y+dir[i][1]] = true;}}}bool check(int x, int y){if(map[x][y] == false || x < 0 || x >= m || y < 0 || y >= n){return false;}return true;}3.组合的输出
题意：排列与组合是常用的数学方法，其中组合就是从N个元素中抽出R个元素（不分顺序且R<=N），我们可以简单地将N个元素理解为1,2，…，N，从中任取R个数。
例如N=5，R=3，所有组合为：123 124 125 134 135 145 234 235 245 345
思路：回溯先放第一个数，再在第一个数字的基础上放第二个数字，再在第二个数字的基础上放第三个数字
代码：
#include <iostream>#include <cstdio>#include <algorithm>#include <string>using namespace std;int ans[25];void dfs(int postion, int value);int n, r;void output();int main(){freopen("compages.in", "r", stdin);freopen("compages.out", "w", stdout);scanf("%d%d", &n, &r);dfs(0, 1);return 0;}void dfs(int postion, int value){if(postion == r){output();return;}if(value > n){return;}for(int i = value; i <= n; ++i){ans[postion] = i;dfs(postion+1, i+1);}}void output(){cout << ans[0];for(int i = 1; i < r; ++i){cout << " " << ans[i];}cout << endl;}
4.关路灯
题意：
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能最省电。他每天都是在天亮时首先关掉自己所在处位置的路灯，然后可以向左向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地掉头有可能会更省一些。
请你为老张编一个程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
思路：当初测试的时候因为DP没有思路就直接写了暴力搜索,结合网上的题解
闹里有钱，静处安身。
