Codeforces 1132E（转化+dp）

要点

假设第i个最后总共选的值为ci，不妨把它分成两部分：$$c_i=cnt'_iL+q_i$$$$L=840,\ 0<=q_i<L$$又可以写成：$$c_i=cnt_1i+cnt_2i$$$$cnt_i'=\frac{cnt_1}{\frac{L}{i}},\ q_i=cnt_2i$$所以$$maxcnt'_i=\frac{cnt[i]-cnt_2}{\frac{L}{i}}$$一会dp要用。
事实上如果只有一个item的话，L取它的倍数即可；而8个数我们为了将它们合在一起算，所以取一个它们的LCM。这样做的目的是$$ans=L\sum_{i=1}^{8{cnt'_i}+\sum_{i=1}}8{q_i}$$而此时$$0<=q_i<=8L$$这个值并不大，我们就可以dp做了。
设dp[i][j]：在前i个数中取、全部的qi为j时，最多的cnt'。这样最后就既有qi又有cnt'，可以直接算出答案。
精简dfs做的大佬tql，学不来学不来……

const int N = 9;

const int L = 840;

ll W, cnt[N], dp[N][L * N];

int main() {

	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> W;

	rep(i, 1, 8)	cin >> cnt[i];

	memset(dp, -1, sizeof dp);

	dp[0][0] = 0;

	rep(fakei, 0, 7) {

		rep(j, 0, L * fakei) {

			if (dp[fakei][j] >= 0) {

				int i = fakei + 1;

				rep(k, 0, min(cnt[i], (ll)(L / i))) {

					dp[i][j + k * i] = max(dp[i][j + k * i], dp[fakei][j] + (cnt[i] - k) / (L / i));

				}

			}

		}

	}

	ll ans = 0;

	rep(j, 0, L * 8) {

		if (j > W)	break;

		if (dp[8][j] >= 0) {

			ans = max(ans, min(dp[8][j], (W - j) / L) * L + j);

		}

	}

	cout << ans << endl;

	return 0;

}

巴特西

Codeforces 1132E（转化+dp）

要点

最新文章

热门文章