Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-02SRM533 Div1

SRM533 Div1 250 CasketOfStar

| 17:22 | SRM533 Div1 250 CasketOfStar - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM533 Div1 250 CasketOfStar - SRM diary(Sigmar) SRM533 Div1 250 CasketOfStar - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

最後の状態から逆に考えれば、範囲を指定したDPができる

書いた

バグっててなかなか治らなかった

半開区間にしたのが失敗だった。もっと考えれば良かった。


ソースコード

int memo[52][52];

class CasketOfStar {
public:
	int n;
	vector <int> weight;

	int rec(int b, int e) {
		int res=0;
		if(e==b+2) return 0;
		if(memo[b][e]>=0) return memo[b][e];

		for(int i=b+1; i<e-1; i++) {
			res=max(res, rec(b, i+1)+rec(i, e));
		}
		res+=weight[b]*weight[e-1];
		memo[b][e]=res;
		return res;
	}

	int maxEnergy(vector <int> weight_) {
		int res;
		weight=weight_;
		n=weight.size();

		memset(memo, -1, sizeof(memo));
		res=rec(0, n);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120302