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;
	}
};