题目链接
题目大意
给你k种类型的物品若干种，一个种类只能选一种物品，求题中DMG的最大值
题目链接
太神奇了，居然就是暴力，但是要预处理这个种类为空时下一个要去的种类，不然会使这个搜索树退化
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug printf("I am here\n");
using namespace std;
typedef long long ll;
typedef pair<int,pair<int,int> > pii;
const int maxn=50+5,mod=998244353,inf=0x3f3f3f3f;
const double eps=1e-10;
int t,n,k,nxt[maxn];
vector<int> opt[maxn][5];
ll ans;
void init(){ans=-1;for(int i=1;i<=50;i++){for(int j=1;j<=4;j++){opt[i][j].clear();}}
}
void dfs(int pos,int a,int b,int c,int d){if(pos==k+1){ans=max(ans,1ll*a*b*c*d);return ;}for(int j=0;j<opt[pos][1].size();j++){dfs(pos+1,a+opt[pos][1][j],b+opt[pos][2][j],c+opt[pos][3][j],d+opt[pos][4][j]);}if((int)opt[pos][1].size()==0){dfs(nxt[pos],a,b,c,d);}
}
int main(){scanf("%d",&t);while(t--){init();scanf("%d%d",&n,&k);for(int i=1,t,a,b,c,d;i<=n;i++){scanf("%d%d%d%d%d",&t,&a,&b,&c,&d);opt[t][1].push_back(a);opt[t][2].push_back(b);opt[t][3].push_back(c);opt[t][4].push_back(d);}int last=k+1;for(int i=k;i>=1;i--){//预处理nxt[i]=last;if((int)opt[i][1].size()!=0){last=i;}}dfs(1,100,100,100,100);printf("%lld\n",ans);}return 0;
}