首页 > 阿里 22号 笔试第二题
头像
皮皮虾爱上派大星
编辑于 2021-07-22 18:46
+ 关注

阿里 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;
}

全部评论

(6) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐