Gym

题意：n个点，给定起点和终点，可以每次可以走一格或两格，走一格则需要一个代价，每个格子只能走一次，问从起点到终点并经过每一个点的最小代价

思路：这题我没看出什么道理，先打了个暴力，结果发现了个相当坑的规律，，然后就过了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 #define MAXN 200005
18 using namespace std;
19 int main()
20 {
21 #ifndef ONLINE_JUDGE
22     freopen("in.txt", "r", stdin);
23     freopen("out.txt", "w", stdout);
24 #endif // OPEN_FILE
25     int n, s, t, o;
26     while(~scanf("%d%d%d", &n, &s, &t)){
27         //printf("%d %d %d %d ", n, s, t, o);
28         int ans;
29         if(s == t){
30             ans = 2;
31         }
32         else{
33             if(s > t){
34                 swap(s, t);
35             }
36             if(t - s == 1){
37                 if(s != 1 && t != n){
38                     ans = -1;
39                 }
40                 else{
41                     ans = 1;
42                 }
43             }
44             else{
45                 int tt = n -s + 1;
46                 int ss = n - t + 1;
47                 if(ss < s){
48                     s = ss;
49                     t = tt;
50                 }
51                 int p;
52                 if(s == 1){
53                     p = t - s - 1;
54                     ans = 1 + p / 3 + (p % 3);
55                 }
56                 else{
57                     p = t - s - 2;
58                     ans = 2 + p / 3  + (p % 3);
59                 }
60             }
61         }
62         if(s == 1 && t == n && n % 3 == 1){
63             ans -= 2;
64         }
65         printf("%d
", ans);
66     }
67     /*while(~scanf("%d%d%d", &n, &s, &t)){
68         memset(vis, 0, sizeof(vis));
69         vis[s] = true;
70         vis[t] = true;
71         ans = INF;
72         dfs(s, 0, 0);
73         if(ans == INF){
74             printf("%d %d %d -1
", n, s, t);
75             continue;
76         }
77         printf("%d %d %d %d
", n, s, t, ans);
78     }*/
79 }

下面是暴力的

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <fstream>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <deque>
 7 #include <vector>
 8 #include <queue>
 9 #include <string>
10 #include <cstring>
11 #include <map>
12 #include <stack>
13 #include <set>
14 #define LL long long
15 #define eps 1e-8
16 #define INF 0x3f3f3f3f
17 #define MAXN 200005
18 int n, s, t;
19 int ans;
20 bool vis[MAXN];
21 using namespace std;
22 void dfs(int x, int cnt, int cost){
23     if(cnt == n - 2){
24         if(abs(x - t) == 1){
25             ans = min(ans, cost + 1);
26         }
27         else if(abs(x - t) == 2){
28             ans = min(ans, cost);
29         }
30         else{
31             return;
32         }
33     }
34     int y;
35     for(int i = 1; i <= 2; i++){
36         int p = i == 1 ? 1 : 0;
37         y = x + i;
38         if(y >= 1 && y <= n && !vis[y]){
39             vis[y] = true;
40             dfs(y, cnt + 1, cost + p);
41             vis[y] = false;
42         }
43         y = x - i;
44         if(y >= 1 && y <= n && !vis[y]){
45             vis[y] = true;
46             dfs(y, cnt + 1, cost + p);
47             vis[y] = false;
48         }
49     }
50 }
51 int main()
52 {
53 #ifndef ONLINE_JUDGE
54     freopen("in.txt", "r", stdin);
55     //freopen("out.txt", "w", stdout);
56 #endif // OPEN_FILE
57 
58     while(~scanf("%d%d%d", &n, &s, &t)){
59         memset(vis, 0, sizeof(vis));
60         vis[s] = true;
61         vis[t] = true;
62         ans = INF;
63         dfs(s, 0, 0);
64         if(ans == INF){
65             printf("-1
");
66             return 0;
67         }
68         printf("%d
", ans);
69     }
70 }