Yukicoder No.158 奇妙なお使い
整礎な感じにしたくてpriority_queue
した結果TLEを生やしていたが、無理矢理やれば通った。
solution
DP。財布の状態からお使い回数への関数$\mathrm{dp} : 11 \times 101 \times 10001 \to \mathbb{N}$。
DP自体は可能であるが依存関係が綺麗でなく、単なる$3$重loopを回すのでは求まらない。 これは以下のようにして回避できる。
- 変化がなくなるまで$3$重loopを繰り返し実行する
- $\mathrm{dp} : \mathbb{N} \times 11 \times 101 \to 10001$とする
- メモ化再帰にする
implementation
変化がなくなるまで回した。最悪計算量が怪しそう。
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> bool setmax(T & a, T const & b) { if (a < b) { a = b; return true; } else return false; }
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
const int N = 10000, N0 = 1000, N1 = 100, N2 = 1;
int main() {
int a0, a1, a2; cin >> a0 >> a1 >> a2;
int db; cin >> db;
int b0, b1, b2; cin >> b0 >> b1 >> b2;
int dc; cin >> dc;
int c0, c1, c2; cin >> c0 >> c1 >> c2;
vector<vector<vector<int> > > dp = vectors(-1, N/N0+1, N/N1+1, N/N2+1);
repeat (i,N/N0+1) repeat (j,N/N1+1) repeat (k,N/N2+1) dp[i][j][k] = -1;
dp[a0][a1][a2] = 0;
int ans = -1;
while (true) {
bool modified = false;
repeat_reverse (i,N/N0+1) repeat_reverse (j,N/N1+1) repeat_reverse (k,N/N2+1) if (dp[i][j][k] != -1) {
setmax(ans, dp[i][j][k]);
auto foo = [&](int de, int e0, int e1, int e2) {
int di = min(i, de / N0); de -= N0 * di;
int dj = min(j, de / N1); de -= N1 * dj;
int dk = min(k, de / N2); de -= N2 * dk;
if (de == 0) {
if (setmax(dp[i-di+e0][j-dj+e1][k-dk+e2], dp[i][j][k] + 1)) {
modified = true;
}
}
};
foo(db, b0, b1, b2);
foo(dc, c0, c1, c2);
}
if (not modified) break;
}
cout << ans << endl;
return 0;
}