JOI 17 本選-団子職人
考察
一つの串団子と、それに含まれる緑色の団子は一対一に対応します。
よって各緑色の団子について、「それを使って串団子を作るか? 作るなら縦と横どちらの向きに作るか?」を考えることにします。
分けては考えられない、つまり「片方の去就によって、もう片方のとれる道が少なくなる」ような緑色の団子の組はどんなものになるでしょうか?
実験をしてみると、ある 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; }