2020杭電HDU-6768多校第2場Lead of Wisdom(暴力DFS)
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=6772 ブログ園食用:https://www.cnblogs.com/lonely-wind-/p/13374448.html CSDN食用:https://blog.csdn.net/qq_43906000/article/details/107569361
Problem Description
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:
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) 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.
Input The first line of the input contains a single integer T (1≤T≤10), the number of test cases.
For each case, the first line of the input contains two integers n and k (1≤n,k≤50), denoting the number of items and the number of item types.
Each of the following n lines contains five integers ti,ai,bi,ci and di (1≤ti≤k, 0≤ai,bi,ci,di≤100), denoting an item of type ti whose attributes are ai,bi,ci and di.
Output For each test case, output a single line containing an integer, the maximum value of DMG.
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
emmm、テーマを見て...爆搜可以らしいですね、DFSを一発やってみました...Aを出してemmmを出したら、それは何も言うことはないようですが、乱数も过ごすことができると闻きましたが、ランキング0 msはすべて乱数が过ぎたばかりでしょうQQQ、私も波乱数を书きました.の一言では言い尽くせないのは私の姿勢が間違っているのかもしれない.
以下はACのDFSコードです.
Problem Description
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:
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) 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.
Input The first line of the input contains a single integer T (1≤T≤10), the number of test cases.
For each case, the first line of the input contains two integers n and k (1≤n,k≤50), denoting the number of items and the number of item types.
Each of the following n lines contains five integers ti,ai,bi,ci and di (1≤ti≤k, 0≤ai,bi,ci,di≤100), denoting an item of type ti whose attributes are ai,bi,ci and di.
Output For each test case, output a single line containing an integer, the maximum value of DMG.
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
emmm、テーマを見て...爆搜可以らしいですね、DFSを一発やってみました...Aを出してemmmを出したら、それは何も言うことはないようですが、乱数も过ごすことができると闻きましたが、ランキング0 msはすべて乱数が过ぎたばかりでしょうQQQ、私も波乱数を书きました.の一言では言い尽くせないのは私の姿勢が間違っているのかもしれない.
以下はACのDFSコードです.
#include
",ans);
}
return 0;
}