R485(Div.2) C. Three displays

3개의 증가수열을 고르고 그 때의 비용이 최소를 찾는 문제다

N^2 DP로 풀었다

d[pos][cnt]로 테이블을 잡고 pos까지 봤고 cnt개 더 고를 수있을 때로 문제를 풀었다

문제 풀고 틀려서 보니 메모이제이션을 안했다 ㅎㅎ

소스 잘 봐야겠따..!

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#define ll long long
#define inf 1e17
using namespace std;
ll arr[3030], cost[3030];
int n;
ll d[3030][5];
 
ll go(ll pos, ll cnt) {
    if (cnt <= 0 || pos > n) return 0;
    if (cnt == 1) return cost[pos];
 
    ll&ret = d[pos][cnt];
    if (ret != -1) return ret;
    ret = inf;
    for (int i = pos+1; i <= n; i++) {
        if (arr[pos] < arr[i]) ret = min(ret, go(i, cnt-1) + cost[pos]);
    }
    return ret;
}
int main() {
    memset(d, -1, sizeof(d));
    scanf(" %d", &n);
 
    for (int i = 1; i <= n; i++) scanf(" %lld", &arr[i]);
    for (int i = 1; i <= n; i++) scanf(" %lld", &cost[i]);
 
        ll ans = inf;
        for (int i = 1; i <= n; i++) ans = min(ans, go(i, 3));
 
        if (ans == inf) ans = -1;
        printf("%lld\n", ans);
    
    
}