h_nosonの日記

競プロなど

yukicoder No.209 Longest Mountain Subsequence

問題
No.209 Longest Mountain Subsequence - yukicoder
N個の整数A_iが与えられる.
A_iを地形の高さだと考えた時に,A_iの部分列から構成される山で,麓に近づくにつれて坂が緩やかになるような山の幅の最大値を求める問題.

解法
ある地点を頂上だと考えた時にそこから左右にどれだけ山を広げることができるかをメモ化再帰で計算する.
今いる地点,前いた地点を状態として与えれば答えは一意に定まるのでその2つの状態をもってメモ化再帰を行う.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

int n;
int a[100];
int rcnt[100];
int lcnt[100];
int dp[100][100];

int right(int now, int prev) {
    if (dp[prev][now])
        return dp[prev][now];
    int i, ret;
    ret = 1;
    REP (i,now+1,n-1) {
        if (a[i] < a[now] && (now == prev || a[now] - a[i] < a[prev] - a[now]))
            ret = max(ret,1+right(i,now));
    }
    return dp[prev][now] = ret;
}

int left(int now, int prev) {
    if (dp[prev][now])
        return dp[prev][now];
    int i, ret;
    ret = 1;
    REP (i,0,now-1) {
        if (a[i] < a[now] && (now == prev || a[now] - a[i] < a[prev] - a[now]))
            ret = max(ret,1+left(i,now));
    }
    return dp[prev][now] = ret;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int i, ans;
        cin >> n;
        rep (i,n) cin >> a[i];
        rep (i,n) fill(dp[i],dp[i]+n,0);
        rep (i,n) rcnt[i] = right(i,i);
        rep (i,n) dp[i][i] = 0;
        rep (i,n) lcnt[i] = left(i,i);
        ans = 0;
        rep (i,n) ans = max(ans,rcnt[i]+lcnt[i]-1);
        cout << ans << endl;
    }
    return 0;
}