アルゴリズムと数学 演習問題集 031 - Taro's Vacation

記事概要

アルゴリズムと数学 演習問題集 031 - Taro's Vacationのとりあえず動くコードと説明．https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ac?lang=ja

注意

アルゴリズム初心者が書いています．時間内の動作は確認してますが、必ずしも最適解ではないです．

とりあえずコード

031_main.cpp

///////////////////////////
// 031 - Taro's Vacation //
///////////////////////////

#include <iostream>
#include <vector>
#include <iomanip>

#define ULL unsigned long long int 

using std::vector;

int main(void) 
{
	//============================== 入力==============================//
	int N;
	std::cin >> N;

	vector<ULL> A(N);
	for (int i = 0; i < N; ++i) {
		std::cin >> A[i];
	}

	//============================== 計算==============================//

	vector<vector<ULL>> dp(2, vector<ULL>(N + 1));

	for (int i = 1; i <= N; ++i) {
		// 今日勉強しないとき
		dp[0][i] = std::max(dp[0][i - 1], dp[1][i - 1]);

		// 今日勉強する時
		dp[1][i] = dp[0][i - 1] + A[i - 1];
	}

	/*
	// dp確認
	for (int i = 0; i < dp[0].size(); ++i) {
		std::cout << std::setw(5) << dp[0][i] << " ";
	}
	std::cout << std::endl;

	for (int i = 0; i < dp[1].size(); ++i) {
		std::cout << std::setw(5) << dp[1][i] << " ";
	}
	std::cout << std::endl;
	*/

	//============================== 出力 ==============================//
	std::cout << std::max(dp[0].back(), dp[1].back()) << std::endl;
}

説明

・太郎君はi日目に勉強するとA_iだけ実力が上がる．
・しかし、太郎君は2日以上連続で勉強できない．
・太郎君のあげることのできる実力の最大値を求めよ．
というのがこの問題の概要です．

この問題はx日目までにあげることのできる実力の最大値が、x-1日目までにあげることのできる実力の最大値から求められます．よって、動的計画法で解くことができる．

ただし、太郎君は2日以上連続して勉強できないため、x-1日目は勉強したかどうかを考慮する必要があります．

このコードの場合、dp[0][i]にはi日目に勉強しなかったときのi日目までにあげることのできる実力の最大値が格納してあり、dp[1][i]にはi日目に勉強した場合の最大値が格納してあります．

i日目に勉強しない場合、i-1日目に勉強をしているかどうかを考慮する必要はありません．よって、dp[0][i]には、i-1日目に勉強した場合と勉強しなかった場合のうち、大きい方が入ります．

対してi日目に勉強をする場合、i-1日目は勉強をしていない必要があります．よって、i-1日目に勉強しなかった場合の上がる実力の最大値と今日勉強することで上がる実力の和で計算できます．つまり、dp[1][i]にはdp[0][i - 1] + A[i - 1]が入ります．(i日目に勉強した場合に上がる実力はA[i-1]に入っています)

最後に最終日に勉強しなかった場合と勉強した場合のうち、大きい方が求める「太郎君があげることのできる実力の最大値」になります．