Submission #1444146

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <time.h>
#define _USE_MATH_DEFINES
#define LL long long
using namespace std;
const double PI = acos(-1.0);

int max_num(int ary[],int length) {
	int max = ary[0];
	for (int i = 1; i < length; i++)
		if (max < ary[i]) max = ary[i];
	return max;
}

int max_ord(int ary[], int length) {
	int max;
	max = max_num(ary, length);
	for (int i = 0; i < length; i++) {
		if (ary[i] == max) return i;
	}
	return -1;
}

int min_num(int ary[], int length) {
	int min = ary[0];
	for (int i = 1; i < length; i++)
		if (min > ary[i]) min = ary[i];
	return min;
}

int min_ord(int ary[], int length) {
	int min;
	min = min_num(ary, length);
	for (int i = 0; i < length; i++) {
		if (ary[i] == min) return i;
	}
	return -1;
}

int n, a[100000];
bool done[100000][1000];
int memo[100000][1000];

int dp(int i, int c) {
	if (done[i][c]) return memo[i][c];
	int res;
	if (i == n - 1)
		res = c;
	else if (i == n - 2)
		res = dp(i + 1, abs(a[i] - a[i + 1])) + c;
	else {
		int res1, res2;
		res1 = dp(i + 1, abs(a[i] - a[i + 1])) + c;
		res2 = dp(i + 2, abs(a[i] - a[i + 2])) + c;
		res = min(res1, res2);
	}
	done[i][c] = true;
	memo[i][c] = res;
	return res;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	cout << dp(0, 0) << endl;
	
}

Submission Info

Judge Result