問題
http://topcoder.bgcoder.com/print.php?id=1897
フィールドの長さとして行の数rと列の数cが与えられる。
rとcの番号は1からスタートする。
合わせて、行列中の特別なフィールドが、(r,c)の形で順番に与えられる。
(1,1)からスタートし、下または右にしか移動して(r,c)まで移動する。
このとき、フィールドを通った回数ごとに、その場合の数を求める。
ただし、フィールドは与えられた順に通った時にしか通った回数は加算されない。
例えば、フィールドの順番１を通った後に順番２以降を通ったら回数は加算されるが、
順番２を通った後に０，１を通っても加算されない。
解き方
格子状の経路の場合の数の求め方の応用。
ｄｐをどう設計するか。
行番号、列番号の他に、フィールドを通った回数、さらに以前に通ったフィールドの順番が必要なことがわかる。
すべての行列で全探索し、
さらにその中で各長さ、各フィールドの順番の和を求める。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[51][51][51][51];
class CountPaths {
public:
vector<int> difPaths(int r, int c, vector<int> fieldrow, vector<int> fieldcol) {
int MOD=1000007,n=fieldrow.size();
memset(dp,0,sizeof(dp));
dp[0][1][0][0]=1;
FORE(i,1,r+1){
FORE(j,1,c+1){
int cur=0;
FORE(k,0,n)if(fieldrow[k]==i&&fieldcol[k]==j)cur=k+1;
FORE(k,0,n+1){
FORE(l,0,51){
if(cur==0)dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j][k][l])%MOD;
else if(cur>l)dp[i][j][k+1][cur]=(dp[i][j][k+1][cur]+dp[i-1][j][k][l])%MOD;
if(cur==0)dp[i][j][k][l]=(dp[i][j][k][l]+dp[i][j-1][k][l])%MOD;
else if(cur>l)dp[i][j][k+1][cur]=(dp[i][j][k+1][cur]+dp[i][j-1][k][l])%MOD;
}
}
}
}
vector<int> ans;
FORE(i,0,n+1){
int ret=0;
FORE(j,0,n+1)ret=(ret+dp[r][c][i][j])%MOD;
ans.push_back(ret);
}
return ans;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[51][51][51][51];
class CountPaths {
public:
vector<int> difPaths(int r, int c, vector<int> fieldrow, vector<int> fieldcol) {
int MOD=1000007,n=fieldrow.size();
memset(dp,0,sizeof(dp));
dp[0][1][0][0]=1;
FORE(i,1,r+1){
FORE(j,1,c+1){
int cur=0;
FORE(k,0,n)if(fieldrow[k]==i&&fieldcol[k]==j)cur=k+1;
FORE(k,0,n+1){
FORE(l,0,51){
if(cur==0)dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j][k][l])%MOD;
else if(cur>l)dp[i][j][k+1][cur]=(dp[i][j][k+1][cur]+dp[i-1][j][k][l])%MOD;
if(cur==0)dp[i][j][k][l]=(dp[i][j][k][l]+dp[i][j-1][k][l])%MOD;
else if(cur>l)dp[i][j][k+1][cur]=(dp[i][j][k+1][cur]+dp[i][j-1][k][l])%MOD;
}
}
}
}
vector<int> ans;
FORE(i,0,n+1){
int ret=0;
FORE(j,0,n+1)ret=(ret+dp[r][c][i][j])%MOD;
ans.push_back(ret);
}
return ans;
}
};