A - Frog 1

A - Frog 1

Solution 01: IH19980412

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include<bits/stdc++.h> using namespace std; #define INF 1<<28 #define MAX 100005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; int n, a[100005]; int dp[MAX]; int main() { FASTIO /* double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif */ cin>>n; for(int i = 1; i <= n; i++) cin>>a[i]; dp[1] = 0; for(int i = 2; i <= n; i++){ dp[i] = dp[i-1] + abs (a[i] - a[i-1]); if(i > 2){ dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2])); } } cout << dp[n]<<endl; // double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Solution 02: colun

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include<bits/stdc++.h> using namespace std; #define INF 1<<28 #define MAX 100005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; int main() { FASTIO /* double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif */ int n,a,b,c,d; cin >> n; a = b = 0; cin >> c; d = c; for(int i = 1; i < n; i++) { int x; cin >> x; a = min(a+abs(x-c), b + abs(x - d)); swap(a,b); c = d; d = x; } cout << b << "\n"; // double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Solution 03:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include<bits/stdc++.h> using namespace std; #define INF 1<<30 #define MAX 100005 #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); typedef long long ll; int main() { FASTIO /* double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif */ int n; cin >> n; vector<int> H(n+10, 0); for(int i = 0; i < n; i++) cin >> H[i]; vector<int> ans(n+5, INF); ans[0] = 0; for(int i = 0; i < n; i++){ ans[i+1] = min(ans[i+1], ans[i] + abs(H[i+1] - H[i])); ans[i+2] = min(ans[i+2], ans[i] + abs(H[i+2] - H[i])); } cout << ans[n-1]<<endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; }

Share: