Lead of Wisdom（HDU 6772）

题目来源：2020杭电多校第二场

题意

给定n件物品，每个物品具有类型t和a,b,c,d四个属性，最大的属性编号为k，每种类型物品选一件，求下列代数式的最大值。

$DMG=(100+\sum_{i\in S}a_i)(100+\sum_{i\in S}b_i)(100+\sum_{i\in S}c_i)(100+\sum_{i\in S}d_i)$

数据范围

10组数据。 $n,k\leq 50, 0\leq a,b,c,d\leq 100$ 时间为8s。

思路

暴力搜索。理论上最大复杂度不超过 $O(3^{50/3})$ 。
要注意的是序号的处理，比如样例还有类型序号为124的物品但是没有3，所以需要离散化。添加空节点会超时，所以先排序之后用set维护当前类型数量。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int ca,n,k;
ll mx = 0;
vector<int> v[55];
set<int> s;

struct node {
    int t,a,b,c,d;
}e[105];

void dfs(int t, int a, int b, int c, int d) {
    if(t==s.size()) {
        mx = max(mx, 1LL*(100+a)*(100+b)*(100+c)*(100+d));
        return;
    }

    for(int i=0;i<v[t].size();i++) {
        dfs(t+1, a+e[v[t][i]].a,b+e[v[t][i]].b,c+e[v[t][i]].c,d+e[v[t][i]].d);

    }
}
int cmp(node x, node y) {
    return x.t < y.t;
}
int main() {
//    freopen("in.txt", "r", stdin);
    scanf("%d",&ca);
    while(ca--) {
        scanf("%d%d",&n,&k);
        memset(e,0,sizeof(e));
        for(int i=0;i<55;i++) v[i].clear();
        mx = 0;
        s.clear();

        for(int i=1;i<=n;i++) {
            scanf("%d%d%d%d%d",&e[i].t,&e[i].a,&e[i].b,&e[i].c,&e[i].d);
            s.insert(e[i].t);
        }
        sort(e+1,e+n+1,cmp);
        int mp[55], id = 0;
        for(set<int>::iterator it=s.begin();it!=s.end();it++) {
            mp[(*it)]=id; id++;
        }
        for(int i=1;i<=n;i++) {
            v[mp[e[i].t]].push_back(i);
        }
        dfs(0,0,0,0,0);
        printf("%lld\n", mx);
    }
}