Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM523 DIV2 HARD - SmallBricks31 (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV2 HARD (1000pt)
Problem Statement

問題概要

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

解法

まず,下の段の全ての状態に対して,一つ上の段の置き方を全部列挙する.
後は,今何段目か,一つ下の段の状態,を状態にして,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 ll long long
#define M 1000000007

int edge[1111][1111];

void edge_gen(int st, int now_mask, int bef_mask){

  if(st==10){
    edge[bef_mask][now_mask]++;
    return;
  }

  edge_gen(st+1, now_mask, bef_mask);

  if(bef_mask & 1<<st) edge_gen(st+1, now_mask|(1<<st), bef_mask);
  if( (bef_mask & 1<<st) && (bef_mask & 1<<(st+1)) ) edge_gen(st+2, now_mask|(1<<st)|(1<<(st+1)), bef_mask);
  if( (bef_mask & 1<<st) && (bef_mask & 1<<(st+2)) ) edge_gen(st+3, now_mask|(1<<st)|(1<<(st+1))|(1<<(st+2)), bef_mask);
}

class SmallBricks31 {
public:
int countWays(int w, int h) {
  int i,j,k;
  int res;
  ll dp[1111], next[1111];

  rep(i,1111) rep(j,1111) edge[i][j] = 0;
  rep(i,1<<w) edge_gen(0, 0, i);

  rep(i,1<<w) dp[i] = 0;
  dp[(1<<w)-1] = 1;
  
  while(h--){
    rep(i,1<<w) next[i] = 0;
    rep(i,1<<w) rep(j,1<<w) next[j] = (next[j] + dp[i]*edge[i][j])%M;
    rep(i,1<<w) dp[i] = next[i];
  }

  res = 0;
  rep(i,1<<w) res = (res+dp[i])%M;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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