2

我正在尝试使用 scala解决以下codechef 问题。问题陈述如下：

哈利波特面前有 n 个混合物，排成一排。每种混合物都有 100 种不同颜色中的一种（颜色的数字从 0 到 99）。

他想把所有这些混合物混合在一起。在每一步，他将取两种并排放置的混合物并将它们混合在一起，然后将得到的混合物放在它们的位置上。

当混合颜色 a 和 b 的两种混合物时，所得混合物的颜色 (a+b) mod 100。

此外，在此过程中会有一些烟雾。混合两种颜色 a 和 b 时产生的烟雾量为 a*b。

找出当把所有混合物混合在一起时哈利能得到的最小烟雾量是多少。

提供的示例答案如下：

输入：

2 
18 
19 
3
40
60
20

输出：

342
2400

在第二个测试用例中，有两种可能：

first mix 40 and 60 (smoke: 2400), getting 0, then mix 0 and 20 (smoke: 0); total amount of smoke is 2400
first mix 60 and 20 (smoke: 1200), getting 80, then mix 40 and 80 (smoke: 3200); total amount of smoke is 4400

第一种情况是正确的方法，因为它可以最大限度地减少产生的烟雾量。

我知道这可以使用动态编程来解决，但我无法解决这个问题并在 scala 中表达算法。

这就是我对这个问题的看法，在某种查找结构中（数组，映射，以 Tuple(Int,Int) 作为键）存储混合两种颜色的所有计算值

这可以通过以下伪代码来完成：

for(colors1<-1 through n)
   for(colors2<-k through n)
      if(color1 != color2)
          //Check if color1,color2 combination exists as (color1,color2) or (color2,color1)    
          Map(color1,color2) = (color1+color2)%100

一旦计算了所有初始颜色，现在我们需要考虑混合颜色的顺序，同时考虑到产生的烟雾。这是我遇到问题的地方。我正在碰壁，试图制定将产生最少烟雾的子结构。

在这里获得一些指导会很棒。

谢谢

4

2 回答 2

1

我编写了以下动态编程解决方案。它也可以作为gist使用。

/** Find the minimum amount of smoke (second) and resulting color (first) 
    by splitting the sequence at every possible position,
    given `lookup` contains the best mix for subsequence. */
def minSmokeMixtureSingle(s: Seq[Int], lookup: Map[Seq[Int],(Int,Int)])
  : (Int,Int) = 
    if(s.size == 1)
        (s(0),0)
    else if(s.size == 2)
        mix(s(0),s(1))
    else {
        val splits = (1 to (s.size - 1)).map(s.splitAt)
        val mixes = splits.map{ case (s1,s2) => 
            val (c1,sm1) = lookup(s1)
            val (c2,sm2) = lookup(s2)
            val (newColor,newSmoke) = mix(c1,c2)
            (newColor, newSmoke + sm1 + sm2)
        }
        mixes.minBy(_._2)
    }

def mix(m1: Int, m2: Int): (Int,Int) = ((m1+m2) % 100, m1*m2)

def minSmokeMixture(s: Seq[Int]) = {
    //create the mixture sequences with increasing length
    val windows = for(windowSize <- 1 to s.size;
        window <- s.sliding(windowSize) ) yield window
    //go over the sequences and compute the lookup-table
    val lookup = windows.foldLeft(Map.empty[Seq[Int],(Int,Int)]){
        case (lu,seq) => lu + (seq -> minSmokeMixtureSingle(seq,lu))
    }
    //simply lookup the result
    lookup(s)
}

println(minSmokeMixture(Seq(18, 19)))
println(minSmokeMixture(Seq(40, 60, 20)))

这当然可以在风格方面得到改进。

它为给定的示例产生正确的输出（第二个数字是烟雾，第一个是最终颜色）：

(37,342)
(20,2400)
于 2012-04-27T14:27:40.140 回答
0

我认为动态编程与它没有太大关系。我认为这是一个图问题，通过广度优先搜索解决。直线最短路径问题。

于 2012-04-27T17:12:49.503 回答