SRM 401 DIV1 Easy - FIELDDiagrams

問題


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;
}

};
このエントリーをはてなブックマークに追加