Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2160-000eaec0
この記事にトラックバックする(FC2ブログユーザー)

SRM523 DIV1 MEDIUM - BricksN (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

問題文の図を参照.
この問題では奥行はすべて1.
最初,幅w (50以下) の土台があって,最高の高さがh以下 (50以下) になるようにブロックを置くパターンの数を mod 1000000007 で求める問題.
使えるブロックは全部高さ1で,幅1以上k以下のものが使用できる.
ブロックを置くときは,置いた場所の下の段には全てブロックがなければいけない.

解法

DP.今考えている一番下の段の,一番左のスペースの位置で場合分けする.
その際,それより左をブロックで詰めるパターンの数が必要になるので,それは最初に別途DPで求めておく.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

ll dp1d[100];
ll dp[100][100];

ll solve(int w, int h){
  int i,j,k;
  ll res=0, tmp;

  if(dp[w][h] >= 0) return dp[w][h];
  if(w==0 || h==0) return dp[w][h] = 1;

  res = solve(w-1, h) + dp1d[w] * solve(w, h-1);
  res %= M;
  
  REP(i,1,w){
    res += ((dp1d[i] * solve(i, h-1))%M) * solve(w-i-1, h);
    res %= M;
  }

  return dp[w][h] = res;
}

class BricksN {
public:
int countStructures(int w, int h, int mx) {
  int i,j,k;
  int res;

  rep(i,100) rep(j,100) dp[i][j] = -1;

  dp1d[0] = 1;
  REP(i,1,100){
    dp1d[i] = 0;
    REP(k,1,mx+1) if(i-k >= 0) dp1d[i] = (dp1d[i] + dp1d[i-k]) % M;
  }

  res = solve(w,h);

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2160-000eaec0
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。