SRM372 div1 medium

お金が500しかないところがなんだかDP臭いのでDPだろうと思って考える。
だいたい出来るけど11の倍数っていう制約が厄介。
"11の倍数"で検索すると
a*1000+b*100+c*10+dという数(a,b,c,dは９以下)があったとき
(a-b+c-d)%11==0なら11の倍数らしい。
それ分かると普通にメモ化再帰できる。

#include <string>
#include <vector>
#include <sstream>
#include <cstdio>
#include <cstring>

typedef long long LL;
using namespace std;

LL cache[32+10][11+10][500+10];

class RoundOfEleven 
{
	public:

		int n;
		string number;

		LL rec(int pos,int diff,int money)
		{
			LL &r=cache[pos][diff][money];

			if(r!=-1)
				;
			else if(pos==n)
				r=(diff==0)?money:0;
			else
			{
				r=0;
				for(int i=0;i<10;i++)
				{
					int m=i+'0'-number[pos];
					m=(0<m)?m:-m;
					int d=(pos%2==0)?i:(11-i);
					if(0<money-m)
						r+=rec(pos+1,(diff+d)%11,money-m);
				}
			}
			return r;
		}

		long long maxIncome(int input, int money) 
		{
			stringstream ss;
			ss<<input;
			ss>>number;
			n=number.size();

			memset(cache,-1,sizeof(cache));
			return rec(0,0,money);
		}
};