距离算法 - 清除所有级别所需的最小硬币 [英] Distance algorithm - minimum coins required to clear all the level
问题描述
输入格式输入的第一行包含2个空格分隔的整数：N =数字游戏中的等级M =武器类型的数量
N行如下。这些行的第i个包含一个长度为M的二进制字符串。如果该字符串的第j个字符为1，则表示我们需要一个类型为j的武器来清除第i个级别。
约束1< = N< = 20 1< = M< = 20
输出格式打印一个整数，这是答案问题。
示例TestCase 1
输入
1 4
0101
输出4
说明此游戏只有一个级别。我们需要两种类型的武器--1和3.因为最初，Thor没有武器，他将不得不购买这些武器，这将花费他2 ^ 2 = 4个硬币。
Sample TestCase 2
输入
3 3
111
001
010
输出3
说明此游戏共有3个等级。 0级（111）需要所有3种类型的武器。第1级（001）只需要2型武器。第2级只需要1型武器。如果按给定顺序清除等级（0-1-2），则总成本= 3 ^ 2 + 0 ^ 2 + 0 ^ 2 = 9个硬币。如果我们按照1-2-0的顺序清除水平，它将花费= 1 ^ 2 + 1 ^ 2 + 1 ^ 2 = 3个硬币，这是最佳方式。
我尝试过的事情：
我知道这可以使用距离算法来完成任何帮助都会受到赞赏
这就是 - 正如你所说 - 竞争性节目。这意味着我们给你的任何帮助都会对你的竞争对手产生不利影响，以及（至少在道德上，如果不一定合法的话）作弊。
一定要研究，问问如果你被困在一个特定的点。但是，只是复制'问题'并说帮助我就像试图让我们做你的作业一样，我们不这样做。
引用：我知道这可以使用距离算法来完成任何帮助都会受到赞赏
我必须丢失很大，因为我甚至没有看到这个问题的难度。即使拥有200个武器和等级。
解决方案是粗暴的力量
制作一系列你拥有的武器
制作一个游泳池等级
只要一些等级保持
检查所有等级的成本并记住最便宜的
购买武器
从游泳池中移除等级
显示总费用
看起来我的强力算法也是一种贪心算法。
Thor is playing a game where there are N levels and M types of available weapons. The levels are numbered from 0 to N-1 and the weapons are numbered from 0 to M-1 . He can clear these levels in any order. In each level, some subset of these M weapons is required to clear this level. If in a particular level, he needs to buy x new weapons, he will pay x^2 coins for it. Also note that he can carry all the weapons he has currently to the next level . Initially, he have no weapons. Can you find out the minimum coins required such that he can clear all the levels?
Input Format The first line of input contains 2 space separated integers: N = the number of levels in the game M = the number of types of weapons
N lines follows. The ith of these lines contains a binary string of length M. If the jth character of this string is 1, it means we need a weapon of type j to clear the ith level.
Constraints 1 <= N <=20 1<= M <= 20
Output Format Print a single integer which is the answer to the problem.
Sample TestCase 1
Input
1 4
0101
Output 4
Explanation There is only one level in this game. We need 2 types of weapons - 1 and 3. Since, initially, Thor has no weapons he will have to buy these, which will cost him 2^2 = 4 coins.
Sample TestCase 2
Input
3 3
111
001
010
Output 3
Explanation There are 3 levels in this game. The 0th level (111) requires all 3 types of weapons. The 1st level (001) requires only weapon of type 2. The 2nd level requires only weapon of type 1. If we clear the levels in the given order(0-1-2), total cost = 3^2 + 0^2 + 0^2 = 9 coins. If we clear the levels in the order 1-2-0, it will cost = 1^2 + 1^2 + 1^2 = 3 coins which is the optimal way.
What I have tried:
I know this can be done using distance algorithms any help would be appreciated
This is - as you say - "Competitive programming". Which means that any help we give you disavantages your fellow competitors, as well as (at least morally, if not necessarily legally) cheating.
Research by all means, ask if you are stuck at a specific point. But to just copy'n'paste the question and say "help me" is the same as trying to get us to do your homework, and we don't do that.
Quote:I know this can be done using distance algorithms any help would be appreciated
I must be missing big, because I do not even see what is the difficulty of this problem. Even with 200 weapons and levels.
The solution is brut force
Make an array of weapons you have Make a pool of the levels As long as some levels remain Check cost of all levels and remember cheapest buy weapons remove the level from pool display total cost
Looks like my brut force algorithm is also a Greedy algorithm.
这篇关于距离算法 - 清除所有级别所需的最小硬币的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
