I’m trying to solve this dp problem.
Link: Question
My Solution: Solution
I have made a ‘tmp’ variable to handle the case where the person cannot do the same activity twice or more in a row. The code does seem to get me partial AC. But its still getting WA in some cases. Could you please help me in finding if I’m missing something. Also do recommend me some new approach maybe.
I think you are referring to C. Vacation problem.
You can do something like this.
#include <iostream>
#include <vector>
#define ll long long
#define vi vector<int>
#define vii vector<ll>
using namespace std;
void file_io()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
file_io();
ll n;
cin >> n;
vector<vii> a(n, vii(3));
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < 3; j++)
{
cin >> a[i][j];
}
}
vector<vii> dp(n, vii(3,-1));
dp[0][0]=a[0][0],dp[0][1]=a[0][1],dp[0][2]=a[0][2];
for (ll i = 1; i < n; i++)
{
dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
dp[i][2]=max(dp[i-1][1],dp[i-1][0])+a[i][2];
}
cout << max(dp[n - 1][0],max(dp[n-1][1],dp[n-1][2])) << endl;
return 0;
}