TopCoder SRM 398 Div1 Medium CountPaths

問題

rxcマスの格子がある。
(1,1)のマスを出発して(r,c)のマスへ最短距離で移動する。
一回の移動では(x,y)から(x+1,y)または(x,y+1)へ移動できる。

マスのなかには特別なものがあり、それぞれの座標は(fieldRow[i],fieldCow[i])により与えられる。
経路上に特別なマスをちょうどi個含み、かつ
特別なマスの訪問順が(fieldRow[i],fieldCol[i])での順序と同じである経路の総数を
0≦i≦fieldRow[]の要素数+1なる全てのiについてmod 1000007で求めよ。

制約条件

r,c≦50
fieldRow[i],fieldCol[i]≦50
fieldRowとfieldColの要素数は等しい。
fieldRowの要素数≦50

方針

DP.
dp[y][x][count][last]を、
(y,x)のマスにいて、今までに特別なマスをcount個通り、最後に通った特別なマスの番号がlastであるような状態に至る総数とする。
ここからy+1またはx+1に移動してテーブルを更新することができる。

ソースコード

const int mod=1000007;
const int dy[]={0,1},dx[]={1,0};
int dp[52][52][52][52];
int num[52][52];

class CountPaths {
  public:
  vector <int> difPaths(int r, int c, vector <int> fieldrow, vector <int> fieldcol) {
    int n=fieldrow.size();
    memset(dp,0,sizeof(dp));
    memset(num,-1,sizeof(num));
    rep(i,n)num[fieldrow[i]][fieldcol[i]]=i;
    
    int sk=0, sl=0;
    rep(i,n)if(fieldrow[i]==1&&fieldcol[i]==1)sk=1, sl=i;
    dp[1][1][sk][sl]=1;
    
    rep(i,r+1)rep(j,c+1)rep(k,n+1)rep(l,n+1)if(dp[i][j][k][l])rep(d,2){
      int y=i+dy[d], x=j+dx[d], nk=k, nl=l;
      if(num[y][x]>=0){
        if(num[y][x]<l)continue;
        nl=num[y][x]; nk++;
      }
      (dp[y][x][nk][nl]+=dp[i][j][k][l])%=mod;
    }
    vi ans;
    rep(i,n+1){
      int sum=0;
      rep(j,n+1)(sum+=dp[r][c][i][j])%=mod;
      ans.pb(sum);
    }
    return ans;
  }
  
};