Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM285 DIV1 EASY/DIV2 MEDIUM - SentenceSplitting (DP解法) (この記事を編集する[管理者用])

Source

TopCoder SRM285 DIV1 EASY (250pt)
TopCoder SRM285 DIV2 MEDIUM (500pt)
Problem Statement

問題概要とか

概略と解法は以前書いた記事を参照.
以下のコードは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)

class SentenceSplitting {
public:
int split(string sentence, int partition) {
  int i, j, k, sum, dp[66][66];
  int n, len[66]; // n=単語数, len=各単語の長さ+1の配列

  partition++;
  j=-1; n=0; sentence+=" ";
  rep(i,sentence.size()) if(sentence[i]==' ') len[n++]=i-j, j=i;

  rep(i,66) rep(j,66) dp[i][j]=1000000000;
  dp[0][0]=0;

  // dp[i][j]の意味は, 単語をi個だけ並べた時, 行をj個使った場合, これまでの最大の行の長さを保存しておく
  rep(i,n) rep(j,partition){
    sum=0; // 次の行の長さ
    REP(k,i,n+1){
      dp[k][j+1]=min(dp[k][j+1],max(sum,dp[i][j]));
      sum += len[k];
    }
  }

  return dp[n][partition]-1;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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