<7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors)

### DP ###

### 2004 TCCC Online Round 4 Div 1 Level 1 ###

<소스코드>

- d[i][j][k] : i번째 차례, j == 0 이면 이전 이웃에게 기부를 받음, k == 1 이면 첫번째 집에서 기부를 받음

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[41][2][2];
 
class BadNeighbors {
public:
    int n;
    int donation(vector<int> &donations, int i, bool prev, bool first) {
        int *ret = &d[i][prev][first];
        if(first && i == n-1) return 0;
        if(!first && i == n) return 0;
        if(*ret) return *ret;
        
        *ret = donation(donations, i+1, 0, first);
        if(!prev) *ret = max(*ret, donation(donations, i+1, 1, first)+donations[i]);
        return *ret;
    }
 
    int maxDonations(vector<int> donations) {
        n = donations.size();
        int ans = donation(donations, 1, 1, 1)+donations[0];
        return max(ans, donation(donations, 1, 0, 0));
    }
};

>> first 가 1 이면 마지막 집은 n-2 번째 집이 되고, first 가 0이면 마지막 집은 n-1번째 집이 된다. (첫번째 집이 0번째 집이라고 생각)

<해설 소스코드>

#include <vector>
using namespace std;
 
class BadNeighbors {
public:
    int maxDonations(vector<int> donations) {
        int i;
        int ans = 0;
 
        int N = donations.size();
        int *dp = new int[N];
 
        for(i=0; i<N-1; i++) {
            dp[i] = donations[i];
            if(i > 0) dp[i] = max(dp[i], dp[i-1]);
            if(i > 1) dp[i] = max(dp[i], dp[i-2]+donations[i]);
            ans = max(ans, dp[i]);
        }
 
        for(i=0; i<N-1; i++) {
            dp[i] = donations[i+1];
            if(i > 0) dp[i] = max(dp[i], dp[i-1]);
            if(i > 1) dp[i] = max(dp[i], dp[i-2]+donations[i+1]);
            ans = max(ans, dp[i]);
        }
 
        delete []dp;
        return ans;
    }
};