Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM527 DIV1 EASY/DIV2 MEDIUM - P8XGraphBuilder (この記事を編集する[管理者用])

Source

TopCoder SRM527 DIV1 EASY (300pt)
TopCoder SRM527 DIV2 MEDIUM (550pt)
Problem Statement

問題概要

0以上,10000以下の整数列a[1], a[2], ..., a[N]が与えられる.
N+1個のノードからなる全域木に対して,点数を以下のように定める.
 次数がkのノードに対して,a[k]点を与える.
 木の点数は,ノードの点数の合計.
全ての全域木の中で,最高点を求める問題.

解法

全域木であるので,ノード数はN+1,次数の合計は2N,次数の最低は1,最大はNを満たさなければいけない.
逆に,それを満たせば,そのような全域木を作ることはできる.
なので,現在使ったのノード数,使った次数を状態にして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 INF 1000000000

class P8XGraphBuilder {
public:
int solve(vector <int> in) {
  int i,j,k,n;
  int dp[1000], next[1000];;

  n = in.size();

  rep(i,1000) dp[i] = -INF;
  dp[0] = 0;

  rep(k,n+1){
    rep(i,1000) next[i] = -INF;
    rep(i,900) if(dp[i] >= 0) REP(j,1,n+1){
      if(next[i+j] < dp[i] + in[j-1]) next[i+j] = dp[i]+in[j-1];
    }
    rep(i,1000) dp[i] = next[i];
  }

  return dp[2*n];
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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