SRM 398 Div1 Medium CountPaths

問題

高さr、幅cの長方形の盤面がある。(1,1)のコマから右隣か上に移動を繰り返してゴールの(r,c)まで行きたい。盤面には特別なコマがいくつかありそれらの位置はfieldrow、fieldcolで与えられる。ゴールに行くまでに特別なコマをx個通る手順数を1000007で割ったあまりをx番目の要素とするような配列を返せ。(0<=x<=特別なコマ数)
ただし、任意の2つの特別コマ(fieldrow[i],fieldcol[i])、(fieldrow[j],fieldcol[j])がi < jという順番である場合、特別コマiを通過した後に特別コマjを通過しても良いが、コマjを通過した後にコマiを通過することはできない。

やりかた

dp。
dp[i][j][k][l]:=（コマ(i,j)に行く手順数。ただし特別なコマをk個通過し、最後に通過した特別なコマの順番がlであるケース。）

特別なコマに順番に番号をふっておき、最後に通過したコマの番号を記録しておけばそのコマより若番の特別なコマに入るケースを除外して考えることができる。あとは普通のdp。

以下ソース

const int MOD = 1000007;
int dp[51][51][51][51];

class CountPaths {
public:
  int N;
  vector <int> difPaths(int r, int c, vector <int> fieldrow, vector <int> fieldcol) {
    N = fieldcol.size();
    int sp[51][51] = {{0}};
    for(int i = 0, idx = 0; i < N; i++)
      sp[fieldrow[i] - 1][fieldcol[i] - 1] = ++idx;
    
    memset(dp, 0, sizeof(dp));
    if(sp[0][0] != 0) dp[0][0][1][sp[0][0]] = 1;
    else dp[0][0][0][0] = 1;
    
    for(int i = 0; i < r; i++){
      for(int j = 0; j < c; j++){
	for(int k = 0; k <= N; k++){
	  for(int l = 0; l <= N; l++){
	    if(sp[i + 1][j] == 0)//上のコマは特別なコマではない
	      dp[i + 1][j][k][l] = (dp[i + 1][j][k][l] + dp[i][j][k][l]) % MOD;
	    if(sp[i + 1][j] > l)//上のコマは特別なコマであり通過できる
	      dp[i + 1][j][k + 1][sp[i + 1][j]] = (dp[i + 1][j][k + 1][sp[i + 1][j]] + dp[i][j][k][l]) % MOD;
	    if(sp[i][j + 1] == 0)//右のコマは特別なコマではない
	      dp[i][j + 1][k][l] = (dp[i][j + 1][k][l] + dp[i][j][k][l]) % MOD;
	    if(sp[i][j + 1] > l)//右のコマは特別なコマであり通過できる
	      dp[i][j + 1][k + 1][sp[i][j + 1]] = (dp[i][j + 1][k + 1][sp[i][j + 1]] + dp[i][j][k][l]) % MOD;
	  }
	}
      }
    }
    vector<int> ans;
    for(int k = 0; k <= N; k++){
      int sum = 0;
      for(int l = 0; l <= N; l++) sum = (sum + dp[r - 1][c - 1][k][l]) % MOD;
      ans.push_back(sum % MOD);
    }
    return ans;
  }
};

最初のコマが特別なコマである場合がひっかけ。