JOI 17 本選-団子職人

問題

https://www.ioi-jp.org/joi/2017/2018-ho/2018-ho.pdf

考察

一つの串団子と、それに含まれる緑色の団子は一対一に対応します。
よって各緑色の団子について、「それを使って串団子を作るか？　作るなら縦と横どちらの向きに作るか？」を考えることにします。
分けては考えられない、つまり「片方の去就によって、もう片方のとれる道が少なくなる」ような緑色の団子の組はどんなものになるでしょうか？
実験をしてみると、ある 2 つの団子が ／ の向きに隣り合っている場合、それぞれ影響しあう可能性があると分かります。逆に、そのように隣り合っていなければ、互いが影響を及ぼすことはありません。
よって各緑色の団子は、

こんな感じで、それぞれ独立に考えていい、いくつかのグループに分けることができます。
各グループ内で作れる串団子の最大数は、例えば左下のほうから、

1. 縦方向に串団子を作る
2. 横方向に串団子を作る
3. 串団子を作らない

の場合分けをしつつ、DP の要領で計算していけばいいです。

コード

ll n,m;
char g[3000][3000];
ll dfs(P p, ll x, ll y, ll z) {
        // x: 縦に団子をとる y: 横に団子をとる z: 団子をとらない
	if(p.first<0||p.second>=m
            ||g[p.first][p.second]!='G') {
		return max(max(x,y),z);
	}
	g[p.first][p.second]='#';
	ll nx=0,ny=0,nz=0;
	nz=max(max(x,y),z);
	if(p.first-1>=0&&p.first+1<n&&
	   g[p.first-1][p.second]=='R'&&g[p.first+1][p.second]=='W') {
		nx=max(x,z)+1;
	}
	if(p.second-1>=0&&p.second+1<m&&
	   g[p.first][p.second-1]=='R'&&g[p.first][p.second+1]=='W') {
		ny=max(y,z)+1;
	}
	p.first--; p.second++;
	return dfs(p,nx,ny,nz);
}

int main() {
	cin>>n>>m;
	REP(i,n) REP(j,m) cin>>g[i][j];
	ll ans=0;
	for(ll i=n-1; i>=0; i--) for(ll j=m-1; j>=0; j--) {
			if(g[i][j]=='G') ans+=dfs(P(i,j),0,0,0);
	}
	cout<<ans<<endl;
}