DFS(剪枝) - Lead of Wisdom - HDU 6772_综合

DFS(剪枝) - Lead of Wisdom - HDU 6772

2020 Multi-University Training Contest 2 1010

题意：

$T组测试数据。$

$给定n件物品，共有k种，每件物品有四种属性a_i,b_i,c_i,d_i，$

$要从k种物品种，每种物品选择一件，$

$使得收益：$

$DMG=(100+∑_{i∈S}a_i)(100+∑_{i∈S}b_i)(100+∑_{i∈S}c_i)(100+∑_{i∈S}d_i)$

$最大，输出最大收益。$

输入：

$首行包括一个正整数T，表示T组测试数据$

$每组数据首行包括两个正整数n,k，$

$接着n行数据，每行包括t_i,a_i,b_i,c_i,d_i，分别表示物品种类和物品的四个属性。$

Sample Input

1
6 4
1 17 25 10 0
2 0 0 25 14
4 17 0 21 0
1 5 22 0 10
2 0 16 20 0
4 37 0 0 0

Sample Output

297882000

数据范围:

$1≤T≤10，1≤n,k≤50，1≤t_i≤k，0≤a_i,b_i,c_i,d_i≤100$

分析：

$记第i种装备的数量为cnt_i，$

$若cnt_i>0，那么选择该物品一定优于不选择该物品。$

$故总方案数为\prod_{i=1}^kmax(cnt_i,1)，其中\sum_{i=1}^kcnt_i≤50，$

$最坏情况为所有cnt_i均相等时，\prod_{i=1}^kmax(cnt_i,1)取最值，$

$假设它们都等于x，则方案总数为x^{\frac{n}{x}}，当x取3时，最大值为3^{\frac{n}{3}}，$

$当n=50时，大约在10^8级别，仍然是可行的计算量。因此，可以考虑爆搜。$

注意！！！：

$对于数量为0的某种物品，应当直接跳过，不能进入搜索，$

$假设第i种物品数量为0，那么当我们枚举第i-1种物品时，就会搜索出cnt_{i-1}个空节点，$

代码：

#include<iostream>
#include<cstring>#define ll long longusing namespace std;const int N=55;int T,n,k;
int cnt[N];
ll ans;
int ne[N];
struct node
{int a,b,c,d;
}w[N][N];void dfs(int u,int a,int b,int c,int d)  
{if(u>k){ll res=(ll )a*b*c*d;ans=max(ans,res);return ;}if(!cnt[u]) {dfs(ne[u],a,b,c,d);return ;}for(int i=1;i<=cnt[u];i++)dfs(u+1,a+w[u][i].a,b+w[u][i].b,c+w[u][i].c,d+w[u][i].d);
}int main()
{cin>>T;while(T--){memset(cnt,0,sizeof cnt);memset(ne,0,sizeof ne);ans=0;cin>>n>>k;for(int i=1;i<=n;i++) {int t;cin>>t;cnt[t]++;cin>>w[t][cnt[t]].a>>w[t][cnt[t]].b>>w[t][cnt[t]].c>>w[t][cnt[t]].d;}int last=k+1;for(int i=k;i;i--){ne[i]=last;if(cnt[i]) last=i;}dfs(1,100,100,100,100);printf("%lld\n",ans);}return 0;
}