TopCoder SRM 317 Div1 Medium CollectingPayment

問題

n個の仕事があり、i番目の仕事はmoment[i]日目にあり、その報酬がearning[i]である。
報酬は、積算されていき、いつでも好きな日に銀行に振り込ませることができる。
ただし、振込みには一回につき、feeの手数料がかかる。

銀行にふりこまれたお金には、1,8,15,22…日目に利息がつき、
その額はA*(rate/1000.0)である。
その日に振り込まれたお金にも利息がつく。
また、仕事をした当日にその日の報酬を振り込ませることもできる。

365日目に得られる銀行口座の残高の最大値を求めよ。

制約条件

n≦50
1≦moment[i]≦365
earning[i]≦1000

方針

動的計画法による。
dp[i][j]を、i日目までで、現在銀行に振り込まれていない報酬の金額をjとするときの、
銀行口座の残高の最大値とする。
i+1日目には、銀行に給料を振り込ませるか、そのまま積算しておくか選ぶことができ、それぞれの場合についてテーブルを更新することができる。

ソースコード

int n, earn[370];
double dp[2][50001];

class CollectingPayment {
	public:
	double maximumProfit(vector <int> earning, vector <int> moment, int fee, int rate) 
	{
		memset(earn,0,sizeof(earn));
		rep(i,earning.size())earn[moment[i]]=earning[i];
		rep(j,50001)dp[0][j]=-INF;
		dp[0][0]=0;
		
		int cur=0, next=1;
		rep(i,365){
			rep(j,50001)dp[next][j]=-INF;
			rep(j,50001)if(dp[cur][j]!=-INF){
				double r=i%7==0?1+rate/1000.0:1;
				dp[next][j+earn[i+1]]=max(dp[next][j+earn[i+1]], dp[cur][j]*r);
				dp[next][0]=max(dp[next][0], (dp[cur][j]+j+earn[i+1]-fee)*r);
			}
			swap(cur,next);
		}
		
		double ans=0;
		rep(i,50001)ans=max(ans,dp[cur][i]);
		return ans;
	}
};