当前位置: 代码迷 >> 综合 >> DFS(剪枝) - Lead of Wisdom - HDU 6772
  详细解决方案

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

热度:5   发布时间:2024-01-31 22:03:12.0

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

2020 Multi-University Training Contest 2 1010

题意:

T T组测试数据。

n k a i , b i , c i , d i 给定n件物品,共有k种,每件物品有四种属性a_i,b_i,c_i,d_i,

k 要从k种物品种,每种物品选择一件,

使 使得收益:

D M G = ( 100 + i S a i ) ( 100 + i S b i ) ( 100 + i S c i ) ( 100 + i S d i ) DMG=(100+∑_{i∈S}a_i)(100+∑_{i∈S}b_i)(100+∑_{i∈S}c_i)(100+∑_{i∈S}d_i)

最大,输出最大收益。

输入:

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

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

n t i , a i , b i , c i , d i 接着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 1≤T≤10,1≤n,k≤50,1≤t_i≤k,0≤a_i,b_i,c_i,d_i≤100


分析:

i c n t i 记第i种装备的数量为cnt_i,

c n t i > 0 若cnt_i>0,那么选择该物品一定优于不选择该物品。

i = 1 k m a x ( c n t i , 1 ) i = 1 k c n t i 50 故总方案数为\prod_{i=1}^kmax(cnt_i,1),其中\sum_{i=1}^kcnt_i≤50,

c n t i i = 1 k m a x ( c n t i , 1 ) 最坏情况为所有cnt_i均相等时,\prod_{i=1}^kmax(cnt_i,1)取最值,

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

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

注意!!!:

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

i 0 i ? 1 c n t i ? 1 假设第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;
}