[BOJ 14501] 퇴사

https://www.acmicpc.net/problem/14501

예전에 모 기업 문제라고 올라왔던 문제이다. 그냥 간단한 DP인데 멍청하게도 갱신되는 구간을 전부다 확인하지 않는 삽질을 많이 했다. 점화식은 30~36을 참고하면 될것이다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 10000
typedef long long ll;
 
using namespace std;
 
int n,arr[3][111],dp[111];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin >>a >> b;
        arr[1][i] = a;
        arr[2][i] = b;
        dp[i] = b;
    }
    
    for(int i=1;i<=n;i++){
        int t = i+arr[1][i];
        for(int j=t;j<=n;j++){
            dp[j] = max(dp[j] , dp[i]+arr[2][j]); //처음 시작되는 그 부분부터 n까지 다 갱신
 
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(i+arr[1][i] <=n+1){
            ans = max(ans , dp[i]);
        }
    }
    cout <<ans <<endl;
    return 0;
}