acash's blog

By acash, history, 4 years ago, In English

Div 3 dp problem polycarp

I need help in understanding the recurrence in below solution especially the significance of this taken variable in the recurrence whose value can be zero or one.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
 
const int N=2e5+5;
 
int n;
string s;
int cache[N][3][2];
 
int dp(int i, int rem, int taken)
{
	if(i==n)
		return (rem==0 && taken==1);
	int &ans=cache[i][rem][taken];
	if(ans!=-1)
		return ans;
	if(!taken)
	{
		if(s[i]!='0')
			ans=max(dp(i+1, (s[i]-'0')%3, 1), (((s[i]-'0')%3)==0) + dp(i+1, 0, 0));
		else
			ans=1+dp(i+1, 0, 0);
	}
	else
	{
		ans=max((((rem+s[i]-'0')%3)==0) + dp(i+1, 0, 0), dp(i+1, (rem+s[i]-'0')%3, 1));
	}
	return ans;
}
 
int32_t main()
{
	IOS;
	memset(cache, -1, sizeof(cache));
	cin>>s;
	n=s.size();
	int ans=dp(0, 0, 0);
	cout<<ans;
	return 0;
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?