BOJ 15486 - 퇴사 2

매우 쉽게 점화식이 나와서 기분이 좋았던 문제다.

 

i일에 일을 받아서 작업을 하면 i+t[i]일에 p[i]원을 받는다.

일을 받지 않고 다음날로 가는 경우에는 dp[i+1]=max(dp[i+1],dp[i])

일을 받아서 하는 경우에는 dp[i+t[i]]=max(dp[i+t[i]],dp[i]+p[i])

 

n+1일까지 일을 할 수 있으므로 dp[n+1]이 구하고자 하는 값이다.

 

int main() {
	fastio;
	int n;
    cin>>n;
    vector<pair<int,int>>arr(n);
    for(auto&[a,b]:arr)cin>>a>>b;
    vector<int>dp(1500001,0);
    for(int i=1; i<=n; i++){
        dp[i+1]=max(dp[i+1],dp[i]);
        dp[i+arr[i-1].first]=max(dp[i+arr[i-1].first],dp[i]+arr[i-1].second);
    }
    cout<<dp[n+1];
	return 0;
}