LightOJ 1217 Neighbor House (II)

Short description :

We are given N houses to soap. And houses are placed in circular position.
Condition to sell : We can not select two Neighbor Houses to sell soap. (1 and n are also Neighbor Houses)
Target : Sell largest number of soap.

---

Solution Idea :

We can solve this problem using Dynamic Programming idea ( Here I use recursive DP).

Let's define state for recursion DP:

1. position (pos) ,
2. is possible to take this position's value (taken),
3. is first position's value taken or not (first).

---

Base case: (pos>=n)
Normal case: (0 base index)

1. If house position (pos)=0 then
1. we can sell and go next house (pos+1) or
2. we can go next house without selling.
2. If taken=1 that means soap sold in previous house so we can not sell to current house so we must go next houese without selling
3. If house position (pos)=n-1 it is last house so we have to check first house.
1. If sold soap in first house we can not sell current house.
2. Otherwise we can sell.

---

If you still need some help for implementation.

#include <bits/stdc++.h>
using namespace std;
int dp[1001][2][2];
int v[1001],n;
int fun(int pos, int taken, bool first){
    if(pos>=n)return 0;
    int &ret = dp[pos][taken][first];
    if(ret!=-1)return ret;
    ret=0;
    if(pos==0){
        ret=fun(pos+1,1,1)+v[pos];//sell in first house and move to next house
        ret=max(ret,fun(pos+1,0,0));//without selling move to next house
    }
    else if(taken or (pos==n-1 and first)){
        ret=fun(pos+1,0,first);//sold in neighbor house so without selling move to next house
    }
    else {
        ret = fun(pos+1,1,first)+v[pos];//sell in current house and move to next house
        ret = max(ret,fun(pos+1,0,first));//without selling move to next house
    }
    return ret;
}
int main(){
    int test,cs=1;
    cin>>test;
    while(test--){
        memset(dp,-1,sizeof dp);
        cin>>n;
        for(int i=0; i<n; i++)cin>>v[i];
        cout<<"Case "<<cs++<<": ";
        cout<<fun(0,0,0)<<endl;
    }
}

---

Tutorial source