TopCoder SRM 502 Div1 Medium TheProgrammingContestDivOne

このパターン何度か見た。
http://community.topcoder.com/stat?c=problem_statement&pm=11357

問題

N問の問題があるコンテストがある。
各問題には初期得点maxPoints[i]、得点減少速度pointsPerMinute[i]、解くのにかかる時間requiredTime[i]が与えられる。

コンテスト開始t分後に問題を解くとmaxPoints[i] - t * pointsPerMinute[i]のスコアを得られる。
当然複数の問題を同時に解くことはできない。

T分のコンテストで得られる最大スコアを求めよ。

解法

状態として[問題番号][経過時間]を持ち、各状態の最大スコアをDPで求めていけばよい。

問題はどの順で問題を解くかである。
開始直後、i,jの順に問題を解いた場合と、j,iの順に問題を解いたときのスコアは以下の通りとなる。

• maxPoints[i]+maxPoints[j] - requiredTime[i]*pointsPerMinute[i] - (requiredTime[i]+requiredTime[j])*pointsPerMinute[j]
• maxPoints[i]+maxPoints[j] - requiredTime[j]*pointsPerMinute[j] - (requiredTime[i]+requiredTime[j])*pointsPerMinute[i]

両者の差は requiredTime[i]*pointsPerMinute[j]とrequiredTime[j]*pointsPerMinute[i]の大小で決まり、それぞれが小さい方の順番で解く方が有利である。
よって、この基準を持って先にN問をソートすることができる。

ll dpdp[55][100001];

class TheProgrammingContestDivOne {
	public:
	int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
		int index[51];
		int N=maxPoints.size();
		int x,y,i,t;
		FOR(i,N) index[i]=i;
		FOR(x,51) {
			FOR(y,N-1) if(pointsPerMinute[index[y]]*(ll)requiredTime[index[y+1]] <
				pointsPerMinute[index[y+1]]*(ll)requiredTime[index[y]]) swap(index[y],index[y+1]);
		}
		
		FOR(i,N+1) FOR(t,T+1) dpdp[i][t]=-1LL<<50;
		dpdp[0][0]=0;
		FOR(i,N) {
			int ii=index[i];
			FOR(t,T+1) {
				dpdp[i+1][t]=max(dpdp[i+1][t],dpdp[i][t]);
				ll nt=t+requiredTime[ii];
				if(nt<=T) dpdp[i+1][nt] = max(dpdp[i+1][nt], dpdp[i][t] + maxPoints[ii] - nt*pointsPerMinute[ii]);
			}
		}
		ll ma=0;
		FOR(i,N+1) FOR(t,T+1) ma=max(ma,dpdp[i][t]);
		
		return (int)ma;
	}
}
||

*まとめ