E - 常ならずグラフ(緑)

CODE FESTIVAL 2014 決勝のE問題、常ならずグラフを解いた。

過去に問題を見て、解説をみて理解できなかったが、今回は解説を見てすんなり理解したので成長を感じた。

解法

結論からいうとDP

dp[i][0または１]:= R[i]まで見て現在(上昇中 0 or下降中 1)の時の最大値　である。

二重ループで、

if (R[i] > R[j])

chmax(dp[i][0], dp[j][1] + 1);

if (R[i] < R[j])

chmax(dp[i][1], dp[j][0] + 1);

とするのが一番のポイント。　

条件を満たす時、過去を使い現在を更新していくイメージ

コード

#include <bits/stdc++.h>

#include "atcoder/all"

using ll = long long;

#define REP(i, n) for (ll i = 0; i < ll(n); i++)

 

#define DDD fixed << setprecision(10)

#define endl "\n"

#define __MAGIC__

ios::sync_with_stdio(false);

cin.tie(nullptr);

using namespace std;

using namespace atcoder;

/*..................DEFINE GLOBAL VARIABLES...................*/

/*.....................DEFINE FUNCTIONS ......................*/

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}

template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}

/*.........................kemkemG0...........................*/

signed main()

{

__MAGIC__

int N;

cin >> N;

vector<int> R(N);

REP(i, N)

cin >> R[i];

// dp[i][0 or 1]:= R[i]まで見た時の最大値 0は今上昇して、１は下降

vector<vector<int>> dp(N, vector<int>(2, -1));

dp[0][0]=dp[0][1]=1;

REP(i, N)

{

FOR(j, 0, i - 1)

{

if (R[i] > R[j])

chmax(dp[i][0], dp[j][1] + 1);

if (R[i] < R[j])

chmax(dp[i][1], dp[j][0] + 1);

}

}

if(max(dp[N - 1][0], dp[N - 1][1])<3){

cout<<0<<endl;

return 0;

}

cout << max(dp[N - 1][0], dp[N - 1][1]) << endl;

return 0;

}