Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM499 DIV1 MEDIUM (550pt)
Problem Statement
SRM499 DIV1 自分の参加記録

問題概要

半角スペースをSPと書き,改行をNLと書くことにする.
50行以下のテキストで,各行,s[k]個の半角スペースがあるものを作りたい.
この時,SPACEキーとDELETEキーとRETURNキーを押す回数の合計数を最小化したい.
カーソルの移動は自由で,
 SPACEキーを押すと,その行のスペースの数が1個増える
 DELETEキーを押すと,その行のスペースの数が1個減る
 RETURNキーを押すと,その行と同じ数だけのスペースを持つ行が,その次の行に付け加わる

解法

 dp[考えてる最初の行][考えている最後の行][元になった行] = 考えてる区間を,元になった行のSPと同じ数の行から作るための最小キー回数
でDPする.
実はgreedyでも出来るらしい.

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

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

int ab(int x){if(x<0) return -x; return x;}

int in[51], n;
int dp[51][51][51];

int solve(int st,int ed,int sp){
  int i,j,k,res = 1000000000, tmp, tmp1, tmp2;

  if(st>ed) return 0;
  if(dp[st][ed][sp]>=0) return dp[st][ed][sp];

  REP(i,st,ed+1){
    tmp = ab(in[sp]-in[i]);
    tmp1 = tmp2 = 1000000000;
    REP(j,st,i+1){
      k = solve(st,i-1,j) + ab(in[i]-in[j]);
      if(tmp1 > k) tmp1 = k;
      k = solve(st,i-1,j) + ab(in[sp]-in[j]);
      if(tmp1 > k) tmp1 = k;
    }
    REP(j,i,ed+1){
      k = solve(i+1,ed,j) + ab(in[i]-in[j]);
      if(tmp2 > k) tmp2 = k;
      k = solve(i+1,ed,j) + ab(in[sp]-in[j]);
      if(tmp2 > k) tmp2 = k;
    }
    tmp += tmp1 + tmp2;
    if(res > tmp) res = tmp;
  }

//  printf("%d %d %d : %d\n",st,ed,in[sp],res);
  return dp[st][ed][sp] = res;
}

class WhiteSpaceEditing {
public:
int getMinimum(vector <int> lines) {
  int i,j,k;
  int res = 1000000000, tmp;

  n = lines.size();
  rep(i,n) in[i] = lines[i];

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

  rep(i,n){
    tmp = solve(0,n-1,i) + in[i];
    if(res > tmp) res = tmp;
  }

  res += n-1;
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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