TopCoder SRM 372 Div1 Medium RoundOfEleven
問題
次のようなゲームがある。
最初moneyのお金を持っていて数字nから出発する。
1ドル払って、nの桁をどれか一つ小さくすることができる。(0は小さくできない)
1ドル払って、nの桁をどれか一つ大きくすることができる。(9は大きくできない)
nが11の倍数になったら、ゲームをやめて残っているmoneyを得ることができる。
ただし、他の人がゲームをやめるのに使った数字は使うことができない。
ゲームに参加できる手下が十分な人数いる。
手下が最適な行動を取るとき、手下が得られる賞金の総額を求めよ。
制約条件
n≦2^31-1
money≦500
方針
数字を一桁ずつ見ていくような動的計画法による。
各桁の数字が一つ定まると、それに対しての最適な数字の動かし方は一通りに定まる。
dp[pos][money][mod]を、pos桁目まで見終えて、moneyの金額を残し、11で割った余りがmodである状態の場合の数とする。
dp[0][money][0]からはじめて、
これを全ての桁について更新する。
Σi*dp[m][i][0]が答えとなる。
ソースコード
int m,d[40]; ll dp[40][600][11]; class RoundOfEleven { public: long long maxIncome(int n, int money) { if(n==0)return money; memset(dp,0,sizeof(dp)); for(m=0;n;n/=10)d[m++]=n%10; reverse(d,d+m); dp[0][money][0]=1; rep(i,m)rep(j,money+1)rep(k,11)rep(l,10){ int nm=j-abs(d[i]-l); int nk=(k*10+l)%11; if(nm>=0)dp[i+1][nm][nk]+=dp[i][j][k]; } ll ans=0; rep(i,money+1)ans+=dp[m][i][0]*i; return ans; } };