Gym - 100637B Lunch 规律

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

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

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define eps 1e-8

 #define INF 0x3f3f3f3f

 #define MAXN 200005

 using namespace std;

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int n, s, t, o;

     while(~scanf("%d%d%d", &n, &s, &t)){

         //printf("%d %d %d %d ", n, s, t, o);

         int ans;

         if(s == t){

             ans = ;

         }

         else{

             if(s > t){

                 swap(s, t);

             }

             if(t - s == ){

                 if(s !=  && t != n){

                     ans = -;

                 }

                 else{

                     ans = ;

                 }

             }

             else{

                 int tt = n -s + ;

                 int ss = n - t + ;

                 if(ss < s){

                     s = ss;

                     t = tt;

                 }

                 int p;

                 if(s == ){

                     p = t - s - ;

                     ans =  + p /  + (p % );

                 }

                 else{

                     p = t - s - ;

                     ans =  + p /   + (p % );

                 }

             }

         }

         if(s ==  && t == n && n %  == ){

             ans -= ;

         }

         printf("%d\n", ans);

     }

     /*while(~scanf("%d%d%d", &n, &s, &t)){

         memset(vis, 0, sizeof(vis));

         vis[s] = true;

         vis[t] = true;

         ans = INF;

         dfs(s, 0, 0);

         if(ans == INF){

             printf("%d %d %d -1\n", n, s, t);

             continue;

         }

         printf("%d %d %d %d\n", n, s, t, ans);

     }*/

 }

下面是暴力的

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define eps 1e-8

 #define INF 0x3f3f3f3f

 #define MAXN 200005

 int n, s, t;

 int ans;

 bool vis[MAXN];

 using namespace std;

 void dfs(int x, int cnt, int cost){

     if(cnt == n - ){

         if(abs(x - t) == ){

             ans = min(ans, cost + );

         }

         else if(abs(x - t) == ){

             ans = min(ans, cost);

         }

         else{

             return;

         }

     }

     int y;

     for(int i = ; i <= ; i++){

         int p = i ==  ?  : ;

         y = x + i;

         if(y >=  && y <= n && !vis[y]){

             vis[y] = true;

             dfs(y, cnt + , cost + p);

             vis[y] = false;

         }

         y = x - i;

         if(y >=  && y <= n && !vis[y]){

             vis[y] = true;

             dfs(y, cnt + , cost + p);

             vis[y] = false;

         }

     }

 }

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     while(~scanf("%d%d%d", &n, &s, &t)){

         memset(vis, , sizeof(vis));

         vis[s] = true;

         vis[t] = true;

         ans = INF;

         dfs(s, , );

         if(ans == INF){

             printf("-1\n");

             return ;

         }

         printf("%d\n", ans);

     }

 }

巴特西

Gym - 100637B Lunch 规律

最新文章

热门文章