問題
http://yukicoder.me/problems/no/393
d個の以下のクエリを処理する。
2つのn1, n2の長さの竹が与えられる。
m個の要求竹長A1~Amが与えられる。
このとき、2つの長さを竹をうまい具合に切り出して、作り出せる要求竹長の竹の最大個数は?
0 < d <= 10
1 <= n1,n2 <= 10^5
1 <= m <= 60
1 <= Ai <= 10^5
帰納的考察(kmjpさんの解法を見た)
1. 溢れ出るDP感
2. とりあえず要求竹長はソートできる
3. 全状態羅列すると、n1*n2=10^10か…
4. むむむむむむ
――壁――
5. ここで重要な考察がある
最善で作れる要求竹長は小さいものから順に選ばれる
つまり、より小さい竹は作れないけど、それより大きい竹は作れるという状況は最善じゃない。
大きい竹を小さい竹に変えれば、余分な竹が増えて、より良くなる。
(強い人はこの辺の考察どうしてるんだろうか。典型?)
6. ということは、要求竹長を昇順でソートしていけば、片方の竹の長さから、もう片方の竹の長さが一意に定まる
Aiまでの要求竹長を全て作れるとしたとき、n1側の竹で長さj使った場合、n2側の竹では長さ((A1~Aiの和)-j)使われている
7. これでDPが作れる
dp[i][j] = i番目までの要求竹長を”全て”使い、n1側の竹を長さjだけ使ったときの最多個数
更新式
A[i]分だけn1側から切り出せるとき、dp[i + 1][j + A[i]] = dp[i][j] + 1
A[i]分だけn2側から切り出せるとき、dp[i + 1][j] = dp[i][j] + 1
8. これだと、iが大きくなるとdpが更新されなくなる場合があるので、dp全体の最大値を取ると答えになる
実装
http://yukicoder.me/submissions/103230
int d; int n1, n2, m; int A[61]; //----------------------------------------------------------------- int dp[61][101010]; void solve() { scanf("%d %d %d", &n1, &n2, &m); rep(i, 0, m) scanf("%d", &A[i]); sort(A, A + m); rep(i, 0, m + 1) rep(j, 0, n1 + 1) dp[i][j] = -1; dp[0][0] = 0; int sum = 0; int ans = 0; rep(i, 0, m) { rep(j, 0, n1 + 1) if (0 <= dp[i][j]) { ans = max(ans, dp[i][j]); int jj = sum - j; if (j + A[i] <= n1) dp[i + 1][j + A[i]] = dp[i][j] + 1; if (jj + A[i] <= n2) dp[i + 1][j] = dp[i][j] + 1; } sum += A[i]; } rep(i, 0, n1 + 1) ans = max(ans, dp[m][i]); cout << ans << endl; } //----------------------------------------------------------------- int main() { scanf("%d", &d); rep(i, 0, d) solve(); }