第十题：Lead of Wisdom
题目：
In an online game, “Lead of Wisdom” is a place where the lucky player can randomly get powerful items.
There are k types of items, a player can wear at most one item for each type. For the i-th item, it has four attributes ai,bi,ci and di. Assume the set of items that the player wearing is S, the damage rate of the player DMG can be calculated by the formula:
DMG=(100+∑i∈Sai)(100+∑i∈Sbi)(100+∑i∈Sci)(100+∑i∈Sdi)
Little Q has got n items from “Lead of Wisdom”, please write a program to help him select which items to wear such that the value of DMG is maximized.
思路
不要这么暴力嘛qaq 哭唧唧~~
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;const int N=110;int n,m;
int cnt[N],nxt[N];
ll e[N][N][5];
ll ans;void dfs(int x,int a,int b,int c,int d)
{if(x>m){ll temp=1LL*a*b*c*d;ans=max(ans,temp);return ;}if(!cnt[x]){dfs(nxt[x],a,b,c,d);return ;}int n=cnt[x];for(int i=1;i<=n;i++){dfs(x+1,a+e[x][i][0],b+e[x][i][1],c+e[x][i][2],d+e[x][i][3]);}
}int main()
{//freopen("test.in","r",stdin);//设置 cin scanf 这些输入流都从 test.in中读取//freopen("test.out","w",stdout);//设置 cout printf 这些输出流都输出到 test.out里面去
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);int T;cin>>T;while(T--){scanf("%d%d",&n,&m);int x;for(int i=0;i<=n;i++) cnt[i]=0;for(int j=0;j<n;j++){scanf("%d",&x);cnt[x]++;for(int i=0;i<4;i++){scanf("%d",&e[x][cnt[x]][i]);}}x=m+1;for(int i=m;i;i--){nxt[i]=x;if(cnt[i]) x=i;}ans=100*100*100*100;dfs(1,100,100,100,100);cout<<ans<<endl;}return 0;
}