DPまとめコンテスト C - Vacation

概要

数列が与えられる。
1以上N以下の各整数iについて、から1つ選び、総和を最大にしたい。
ただし、連続するiで同じ種類の数列の数値をとれないものとする。総和の最大値を出力せよ。

制約

方針

dp[i][j] : i日目に行動j(0:a, 1:b, 2:c)を行った時の幸福度の総和の最大値 としてDPする。

解答

Submission #3939799 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
	ll a[n], b[n], c[n];
	rep(i, n) cin >> a[i] >> b[i] >> c[i];
 
	ll dp[n+1][3];
	// dp[i][j] : i日目に行動j(0:a, 1:b, 2:c)を行った時の幸福度の総和の最大値
 
	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[0][2] = 0;
 
	for(int i = 1; i <= n; i++){
		dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i-1];
		dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i-1];
		dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + c[i-1];
	}
 
	cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
}