Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-12-22SRM527 Div1

SRM527 Div1 275 P8XGraphBuilder

| 01:20 | SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

Treeになるということで、何かメモ化再帰すればいいんだろう

多少悩みながら以下の方針を思いつく

  • あるTreeが既に途中まで作られているとして、リーフ数と未使用のエッジ数を状態とする
  • 適当なリーフに総当たりで子をくっつけて新しいTreeを作る

何か本番はやっぱりテンパッてしまうようで随分時間がかかってしまった


ソースコード

const int INF=1000000000;
int memo[52][52];

class P8XGraphBuilder {
public:
	int n;
	vector <int> scores;

	int rec(int cnode, int edge) {
		int res=0;
		if(cnode==0) return 0;
		if(memo[cnode][edge]>=0) return memo[cnode][edge];

		for(int i=0; i<=edge; i++) {
			res=max(res, rec(cnode-1+i, edge-i)+scores[i]);
		}

		memo[cnode][edge]=res;
		return res;
	}

	int solve(vector <int> scores_) {
		int res=0;

		scores=scores_;
		n=scores.size();

		memset(memo, -1, sizeof(memo));
		for(int i=1; i<=n; i++) {
			int tres=scores[i-1];
			tres+=rec(i, n-i);
			res=max(res, tres);
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111222