ゴリ押し嘘解法で解いてしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=15944&rd=17805
問題
N個の機械がある。
各機械iは、毎日最大1枚のコインを出すことができ、その価値はV[i]である。
ただし同じ機械を連日使うことができず、連続するD[i]日に1日はコインを出さない日がなければならない。
また、それとは別に、連続するK日に1日は全機械コインを出さない日を設けなければならない。
M日で得られるコインの総価値の最大値を求めよ。
解法
後者の条件、すなわちP日間のうちP日目を全機械止める日、とすると、残り(P-1)日で出せるコインの最大枚数は各機械で確定する。
f(P)をその時の価値とする。
また、それを複数回組み合わせて計Q日間で出せるコインの価値の最大値をg(Q)とする。
g(Q)は、合計がQとなる数列L[j]におけるf(L[i])の総和の最大値となる。
また、求めたいのはg(M+1)である。
さて以下はゴリ押し嘘解法。
Mはとても大きい場合、基本的にほとんどは1日当たりの価値(f(x)/x)が最大となるx日周期でf(x)を獲得していくのが賢いはず。
そこで、g(1)~g(K^2)程度まで愚直にdpで求め、余った日付をx日単位で区切ることにしよう。xは1~Kまで総当たりすればよい。
この解法はO(K^3)かかるが、1.8sぐらいで何とか間に合う。
公式解法は、g(Q)をg(Q/2-x)とg(Q/2+x)でおよそ半々に分割していくメモ化再帰のようだ。
ll V[1010]; ll dp[1010101]; class CollectingCoins { public: long long maxValue(int m, int k, vector <int> v, vector <int> d) { int N=v.size(); int i,j; m++; for(i=1;i<k;i++) { V[i+1]=0; FOR(j,N) { int num=i/d[j]*(d[j]-1)+i%d[j]; V[i+1]+=num*v[j]; } } ZERO(dp); for(i=1;i<=k;i++) dp[i]=V[i]; for(i=1;i<=1000000;i++) { for(j=2;j<=k;j++) dp[i+j]=max(dp[i+j],dp[i]+dp[j]); } ll ma=0; for(i=2;i<=k;i++) { int cur=m%i; int lef=(m-cur)/i; while(cur<=1000000 && cur<=m) { ma=max(ma,dp[cur]+1LL*lef*dp[i]); cur+=i; lef--; } } return ma; } }
まとめ
SRMのサーバはスペックに差があるのか、テストのたびに1.1s~1.8sぐらいで揺れる気がする…。