기타리스트

AOJ 기타리스트 1495

DP문제

SOL) 0보다 작거나 기준 값 보다 커지면 재귀 종료
        그냥 잘 따라가면 답 나온다.

[-] Collapse

#include<cstdio>
#include<cstring>
#define max(a,b) a > b ? a : b
int cache[2000][101], arr[101];
int n, s, m, ans = 0;
int search(int val, int idx){
    if (val < 0 || val > m) return -1000000;
    if (idx == n) return val;
    int& ret = cache[val][idx];
    if (ret != -1) return ret;
    ret = max(search(val - arr[idx+1], idx+1), search(val + arr[idx+1], idx+1));
    return ret;
}
int main(){
    memset(cache, -1, sizeof(cache));
    scanf("%d%d%d", &n, &s, &m);
    for (int i = 1; i <=n; i++)
        scanf("%d", &arr[i]);
    int ans = search(s, 0);
    printf(ans < 0 ? "-1" : "%d", ans);
}