阿里 22号 笔试第二题

记录一下阿里笔试的第二题,笔试的时候没过,后面想了一下就是个三路dfs,自己还是太年轻了。

int n, m, A, B, C;
vector<vector<pair<int, int>>> flag;
vector<int> res1, res2, res3;
void do_dp(int pos, vector<int>& res) {
	int tol = flag[pos].size();
	vector<vector<int>> st(tol+1, vector<int>(m + 1, 0));
	for (int i = 1; i <= tol; i++) {
		for (int j = 0; j <= m; j++) {
			st[i][j] = st[i - 1][j];
			int cost = flag[pos][i - 1].second;
			if (j >= cost) {
				st[i][j] = max(st[i][j], st[i][j - cost] + flag[pos][i - 1].first);
			}
		}
	}
	for (int i = 0; i <=m; i++) {
		res.push_back(st[tol][i]);
	}
}

int main() {
	C = 0;
	cin >> n >> m >> A >> B;
	flag.resize(3);
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) flag[0].push_back({ b,c });
		else if (a == 2) flag[1].push_back({ b,c });
		else flag[2].push_back({ b,c });
	}

	do_dp(0, res1);
	do_dp(1, res2);
	do_dp(2, res3);
	int res = 0;
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j + i <= m; j++) {
			int k = m - i - j;
			res = max(res, (A + res1[i]) * (B + res2[j]) + res3[k]);
		}
	}
	cout << res << endl;
	return 0;
}

#笔试题目##阿里巴巴#
全部评论
能发一下题目吗?
点赞
送花
回复 分享
发布于 2021-07-22 17:28
好难啊,理解题意都费劲
点赞
送花
回复 分享
发布于 2021-07-22 20:10
蔚来
校招火热招聘中
官网直投
感觉是一道完全背包问题,数组a看起来没啥用
点赞
送花
回复 分享
发布于 2021-07-23 09:51
我当时三路爆搜,就20%,然后判断了个极端条件,30%
点赞
送花
回复 分享
发布于 2021-07-24 13:05
这不是背包吗
点赞
送花
回复 分享
发布于 2021-07-25 13:30
背包和记忆深搜殊途同归。
点赞
送花
回复 分享
发布于 2021-08-22 22:33

相关推荐

3 17 评论
分享
牛客网
牛客企业服务