1010.Lead of Wisdom (dfs / 暴力求和) 2020 Multi-University Training Contest 2

本文主要是介绍1010.Lead of Wisdom (dfs / 暴力求和) 2020 Multi-University Training Contest 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

在这里插入图片描述

思路：

题意：给出 n 个技能，每个技能有 4 个属性: a , b , c , d ，每个技能属于一个分类，最多有 k 个分类，每个分类的技能只能学一种，假如最后选定的技能集合为 S，最终可以造成的伤害为题中所给公式。求最大的伤害为多少？
直接DFS递归求出一类技能的伤害值并取个max即可，最复杂的情况就是 2^15 次，最多也就不过千万级。

代码实现：

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9 + 7;
const int  N = 2e5 + 5;ll T, n, k;
ll t, a, b, c, d, ans, id;struct node{ll a, b, c, d;
};vector<node> vt[60];
map<int, int> vis;void dfs(int u, int cnt, ll a, ll b, ll c, ll d){if(cnt == id){ans = max(ans,(100LL+a)*(100LL+b)*(100LL+c)*(100LL+d));return;}for(auto it : vt[u]) dfs(u+1, cnt+1, a+it.a, b+it.b, c+it.c, d+it.d);}signed main()
{IOS;cin >> T;while(T --){cin >> n >> k;for(int i = 0; i <= n; i ++) vt[i].clear();vis.clear();id = 1, ans = 0;while(n --){cin >> t >> a >> b >> c >> d;if(!vis[t]) vis[t] = id ++;vt[vis[t]].push_back({a, b, c, d});}dfs(1,1,0,0,0,0);cout << ans << endl;}return 0;
}