はまやんはまやんはまやん

hamayanhamayan's blog

2本の竹 [yukicoder 393]

問題

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();
}