Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

要素数Nの整数列が与えられる.各整数は1以上1000以下.
要素数が3以上なら,ある要素を消して,その両隣の数字の積を得点として得ることができる.
両端の要素は消せない.
最高得点を求める問題.
DIV1ではNは50以下.
DIV2ではNは10以下.

解法

逆から考える.
最初,両端の要素しかなく,まだ挿入してない要素を挿入すると,その両端の要素の積が得点として得られるとする.
すると,要素を挿入すると,それより左と右の区間は独立に考えることができるので,区間を状態としてDPすれば良い.
DIV2では全探索も可能.

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

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

int n;
int in[100];
int dp[100][100];

int solve(int st, int ed){
  int i,j,k;
  int res = 0, tmp;

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

  REP(i,st+1,ed){
    tmp = solve(st,i) + solve(i,ed) + in[st]*in[ed];
    if(res < tmp) res = tmp;
  }

  return dp[st][ed] = res;
}

class CasketOfStar {
public:
int maxEnergy(vector <int> weight) {
  int i,j,k;
  int res;

  n = weight.size();
  rep(i,n) rep(j,n) dp[i][j] = -1;
  rep(i,n) in[i] = weight[i];

  res = solve(0, n-1);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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