SRM 502 500pt: TheProgrammingContestDivOne

keyword

動的計画法　C++

問題概要

CodeForces形式のコンテストで時間内に最大何点取れるか求める問題。

解法

ある2つの問題を、どちらを先に解けば良いか考えたとき、初期点数をM、必要な時間をR、減少率をPとすると、iよりjを先に解いた方が得点が高い⇔M[i]-R[i]*P[i]+M[j]-(R[i]+R[j])*P[j]

感想

どの問題を解くか決めることができれば夏合宿の問題に落ちるのにそこに落とせないと思いながら解いていた。Standingを見ながらこれだけ出しているんだからGreedyかDPに違いないと思い込んでいたのに何故かDP解法が出なかった(自分は結構、「あの人は最大流知らないはずなのに提出してる→これは最大流使わないんだ」みたいな推測をする。邪道だとは分かっているけど)。
実装中はオーバーフローをうっかりしていたけどサンプル２が弾いてくれた。
あと、この問題って減少率が負のときも同じ解き方できるんだろうか、と思った。推移律が必要な気もするけど。

struct problem{
	int M, p, time;
};

bool operator<(const problem& a, const problem& b){
	return (int64)a.time*b.p < (int64)b.time*a.p;
}

class TheProgrammingContestDivOne {
public:
int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
	int N = (int)maxPoints.size();
	vector< vector<int> > dp(N+1, vector<int>(T+1, -1));
	vector<problem> probs;
	for(int i=0; i<N; i++){
		probs.push_back((problem){maxPoints[i], pointsPerMinute[i], requiredTime[i]});
	}
	sort(probs.begin(), probs.end());
	dp[0][0] = 0;
	for(int i=0; i<N; i++){
		int M = probs[i].M, t = probs[i].time, p = probs[i].p;
		for(int j=0; j<=T; j++)if(dp[i][j] >= 0){
			dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
			if(j + t <= T){
				int64 point = M - (int64)(t+j)*p;
				if(point > 0){
					dp[i+1][j+t] = max(dp[i+1][j+t], dp[i][j] + (int)point);
				}
			}
		}
	}
	return *max_element(dp[N].begin(), dp[N].end());
}