rum3r's blog

By rum3r, history, 3 weeks ago, In English

What am I doing wrong in this problem?

inline void solve(){
		ll n;
		cin >> n;
		ll a[n], b[n];
		for(int i=0; i<n; ++i) {
			cin >> a[i];
		}
		for(int i=0; i<n; ++i) {
			cin >> b[i];
		}
		ll dp[3][n];
		dp[0][0] = a[0];  //selecting first person
		dp[1][0] = b[0];  //selecting second person
		dp[2][0] = 0;     //not selecting anyone
		for(int i=1; i<n; ++i) {
			dp[0][i] = max(dp[1][i-1]+a[i], max(dp[2][i-1]+a[i], dp[2][i-1]+b[i])); //for first person
			dp[1][i] = max(dp[0][i-1]+b[i], max(dp[2][i-1]+a[i], dp[2][i-1]+b[i])); //for second person
			dp[2][i] = max(dp[0][i-1], dp[1][i-1]);  //for not selecting
		}
		cout << max(dp[0][n-1], dp[1][n-1]) << endl;  //taking max over all..
}

PROBLEM Any help would be appreciated.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

The problem is with your DP relation. In the final loop where you are filling in the states, In dp[0][i] you should not consider the case where you are choosing a person from the second row and similarly, In dp[1][i] you should not consider the case where you are choosing a person from the first row. Updated Correct Submission — Link

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks for giving your valuable time brother. I got it! I just want to ask, In tutorial how are they calculating the dp without array ??

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You see that the ith states of our DP (dp[i]) depend only on the (i-1)st states (dp[i-1]). So Instead of storing the values of all the previous states in an array, In the tutorial, only the values to the previous state are being stored.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thanks, Buddy you're the nicest person on CF that I have ever met. Thanks for your help. :D