2288-Oh, My Goat!

Oh, My Goat! | Aizu Online Judge
本番では解けなかった問題

解法

メモ化再帰．
現在のノードと何文字目かでDFS
600*5*600*5だとメモリが足りなくなるので，二つ目のグラフにおいて0文字目の時のみメモするようにする．

実装(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int MOD=1000000007;
struct Edge{
  int src,dst;
  string s;
};
int n[2],m[2];
vector<int> G[2][600];
Edge edge[2][600];
int dp[600][5][600];
int dfs(int now1,int x1,int now2,int x2);
int dfs2(int now1,int x1,int now2,int x2){
  char t=edge[0][now1].s[x1];
  int ans=0;
  if(edge[1][now2].s.size()==x2+1){
    for(int i=0;i<G[1][edge[1][now2].dst].size();i++){
      Edge &next=edge[1][G[1][edge[1][now2].dst][i]];
      if(next.s[0]==t){
        ans+=dfs(now1,x1,G[1][edge[1][now2].dst][i],0);
        ans%=MOD;
      }
    }
  }else{
    if(edge[1][now2].s[x2+1]==t){
      ans+=dfs(now1,x1,now2,x2+1);
      ans%=MOD;
    }
  }
  return ans;
}
int dfs(int now1,int x1,int now2,int x2){//現在いる頂点,1を進める
  if(x2==0){
    if(dp[now1][x1][now2]>=0)return dp[now1][x1][now2];
  }
  int ans=0;
  if(edge[0][now1].s.size()==x1+1){
    if(edge[0][now1].dst==n[0]-1&&edge[1][now2].s.size()==x2+1&&edge[1][now2].dst==n[1]-1)return 1;
    for(int i=0;i<G[0][edge[0][now1].dst].size();i++){
      ans+=dfs2(G[0][edge[0][now1].dst][i],0,now2,x2);
      ans%=MOD;
    }
  }else{
    ans+=dfs2(now1,x1+1,now2,x2);
    ans%=MOD;
  }
  if(x2==0)dp[now1][x1][now2]=ans;
  return ans;
}
int main() {
  int T;
  for(cin>>T;T--;){
    for(int i=0;i<2;i++){
      cin>>n[i]>>m[i];
      for(int j=0;j<n[i];j++){
        G[i][j]=vector<int>();
      }
      for(int j=0;j<m[i];j++){
        int a,b;string c;
        cin>>a>>b>>c;
        edge[i][j]=(Edge){a,b,c};
        G[i][a].push_back(j);
      }
    }
    memset(dp,-1,sizeof(dp));
    int ans=0;
    for(int i=0;i<G[0][0].size();i++){
      for(int j=0;j<G[1][0].size();j++){
        if(edge[0][G[0][0][i]].s[0]==edge[1][G[1][0][j]].s[0]){
          ans+=dfs(i,0,j,0);
          ans%=MOD;
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}