SRM372 div1 medium
お金が500しかないところがなんだかDP臭いのでDPだろうと思って考える。
だいたい出来るけど11の倍数っていう制約が厄介。
"11の倍数"で検索すると
a*1000+b*100+c*10+dという数(a,b,c,dは9以下)があったとき
(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); } };