杭电多校第二场 1010 Lead of Wisdom 题解

题目大意

有n件装备，总共有k种。每种装备最多选一件，每件装备都有abcd四个属性$\large DMG=\left(100+\sum_\limits{i\in S} a_i\right)\left(100+\sum_\limits{i\in S} b_i\right)\left(100+\sum_\limits{i\in S} c_i\right)\left(100+\sum_\limits{i\in S} d_i\right)$

求这个式子的最大值。

解题思路

刚开始看到这个题目的时候，发现这个数据不大，就想着应该可以暴力搜索。

但是t了好几遍，就没写了。

后面比完了看题解，？怎么和我的思路一模一样。

但是我的t了。

结果发现我vector忘初始化了。

吐了，被自己蠢哭了。

后面初始化之后就过了。

唉。。希望自己不要再犯这么低级的错误了。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll ans;
int flag[55];
typedef struct {
	int a, b, c, d;
}T;
int k;
vector<T> e[55];
vector<int> v;

ll cal(ll a, ll b, ll c, ll d) {
	return (100 + a) * (100 + b) * (100 + c) * (100 + d);
}

void slove(int t,int j,ll a,ll b,ll c,ll d) {
	for (auto x : e[t]) {
		a += x.a, b += x.b, c += x.c, d += x.d;
		if (j==v.size()-1) {
			ans = max(ans, cal(a, b, c, d));
		}
		else {
			slove(v[j+1],j+1, a, b, c, d);
		}
		a -= x.a, b -= x.b, c -= x.c, d -= x.d;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		memset(flag, 0, sizeof(flag));
		int n;
		cin >> n >> k;
		v.clear();
		for (int i = 1; i <= k; i++)	e[i].clear();
		for (int i = 1; i <= n; i++) {
			int ty;
			cin >> ty;
			if (!flag[ty])	v.push_back(ty);
			flag[ty] = 1;
			T a;
			cin >> a.a >> a.b >> a.c >> a.d;
			e[ty].push_back(a);
		}
		ans = 0;
		slove(v[0],0, 0, 0, 0, 0);
		cout << ans << endl;
	}
	return 0;
}