2579

점화식

dp[pos][prev step] : 이전 스텝이 pre step 이고 현재 위치가 pos 일때 최대값

dp[p][1] = dp[p-1][2] + data[p]

dp[p][2] = max(dp[p-2][1], dp[p-2][2]) + data[p]

나는 재귀형태로 그냥 풀었다.

소스코드

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

int n,data[301],dp[301][3];

int solve(int pos, int pstep){

if(pos==n) return 0;

else if(pos>n) return -10000000;

int &ret = dp[pos][pstep];

if(ret != 0) return ret;

ret = -10000000;

for(int i=1; i<3; i++){

if(pstep==1 && i==1) continue;

ret = max(ret, solve(pos+i,i)+data[pos+i]);

}

return ret;

}

int main () {

freopen("sample.txt", "r", stdin);

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",data+i);

printf("%d\n",max(solve(1,0)+data[1], solve(2,0)+data[2]));

return 0;

}