No.158 奇妙なお使い - yukicoder
- dp で解く問題。
- 状態数の上限が 10^7 程度なので一回の calc を高速化できればよい。できるだけ小さい金額の貨幣が残る方が Db,Dc との一致確率があがるので下記 calc 内部ではそのように実装している。
array<int,3> A,B,C;
int Db,Dc;
ll dp[11][101][10001];
class StrangeErrand {
public:
ll calc(int a, int b, int c) {
if (dp[a][b][c] >= 0)
return dp[a][b][c];
ll maxCnt = 0;
REP(i,2)
{
int aa = a;
int bb = b;
int cc = c;
int dd = i==0? Db : Dc;
array<int,3> D = i==0? B : C;
while(aa && dd >= 1000)
{
--aa;
dd -= 1000;
}
while(bb && dd >= 100)
{
--bb;
dd -= 100;
}
if (dd <= cc)
maxCnt = max(maxCnt, calc(aa+D[0], bb+D[1], cc-dd+D[2])+1);
}
return dp[a][b][c] = maxCnt;
}
void solve(void) {
REP(i,3) cin>>A[i];
cin>>Db;
REP(i,3) cin>>B[i];
cin>>Dc;
REP(i,3) cin>>C[i];
REP(i,11)
REP(j,101)
REP(k,10001)
dp[i][j][k] = -1;
cout<<calc(A[0],A[1],A[2])<<endl;
}
};