AtCoder

ABC040 C問題(柱柱柱柱柱)を解く

AtCoder_ABC040_C

AtCoder が提供しているABC(AtCoder Beginner Contest)040 C問題をC++で解いてみました。ABC040は、2016年6月18日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 柱柱柱柱柱(Difficulty : 896(参考値))

問題の詳細は、リンク先をご覧ください。

ABC040 C問題 柱柱柱柱柱

DPで解ける典型問題です。AtCoder Problems による Difficulty は 896(参考値)でした。

解答案

C++ プログラム例(ABC040C)

DP(動的計画法)で解ける典型的な問題です。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	vector<int> dp(n + 1, 0);
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = abs(a[2] - a[1]);
	for (int i = 3; i <= n; i++) {
		dp[i] = min(abs(a[i] - a[i - 1]) + dp[i - 1],
					abs(a[i] - a[i - 2]) + dp[i - 2]);
	}

	cout << dp[n] << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

最後に

ABCについては、古い方が典型的な問題であるような気がします。引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA