問題
http://community.topcoder.com/stat?c=problem_statement&pm=8776&rd=12173
整数fieldDiagramが与えられて、fieldDiagram行からなるBOXを作る。
各行0,1,2,...において、長さはそれぞれfieldDiagram,fieldDiagram-1,fieldDiagram-2以下で
なければならない。
また、各行において上の行以下の長さでなければならない。
このような条件を満たすようなBOXの作り方の総数を求める。
解き方
上の行における長さがわかっていれば、上から順にたどっていくことで総数が
計算できるのでdpで解ける。
すべて0の場合は空になるので、最後にそのケース1通りを引いてあげれば良い。
コード
class FIELDDiagrams {
public: long long countDiagrams(int f) {
long long dp[f+1][f+1];
memset(dp,0,sizeof(dp));
dp[0][f]=1LL;
FORE(i,0,f)FORE(j,0,f+1){
for(int k=min(j,f-i);k>=0;k--)dp[i+1][k]+=dp[i][j];
}
long long ret=0;
FORE(i,0,f+1)ret+=dp[f][i];
return ret-1;
}
};
public: long long countDiagrams(int f) {
long long dp[f+1][f+1];
memset(dp,0,sizeof(dp));
dp[0][f]=1LL;
FORE(i,0,f)FORE(j,0,f+1){
for(int k=min(j,f-i);k>=0;k--)dp[i+1][k]+=dp[i][j];
}
long long ret=0;
FORE(i,0,f+1)ret+=dp[f][i];
return ret-1;
}
};