Dada uma lista de altura do horizonte inteiro não negativa, responda quantas pinceladas horizontais ininterruptas com 1 unidade de altura são necessárias para cobri-la.

[1,3,2,1,2,1,5,3,3,4,2], visualizado como:

      5    
      5  4 
 3    5334 
 32 2 53342
13212153342

precisa de nove pinceladas:

      1    
      2  3 
 4    5555 
 66 7 88888
99999999999

Exemplos

[1,3,2,1,2,1,5,3,3,4,2] → 9

[5,8] → 8

[1,1,1,1] → 1

[] → 0

[0,0] → 0

[2] → 2

[2,0,2] → 4

[10,9,8,9] → 11

JavaScript (Node.js) , 38 bytes

a=>a.map(v=>(n+=v>p&&v-p,p=v),p=n=0)|n

Experimente online!

Simplesmente um algoritmo ganancioso que escaneia da esquerda para a direita, apenas desenha linhas se necessário e desenha o maior tempo possível.

Obrigado Arnauld, economize 2 3 bytes

05AB1E ,  8 7  5 bytes

Guardado 2 bytes graças a @Adnan

0š¥þO

Experimente online!

Quão?

Isso está usando o algoritmo encontrado pela primeira vez por @tsh . Se você gosta desta resposta, não deixe de votar também na resposta !

Cada vez que um arranha-céu é menor ou igual ao anterior, ele pode ser pintado 'de graça', simplesmente estendendo as pinceladas.

Por exemplo, pintar arranha-céus $B$ e $C$ na figura abaixo não custa nada.

Por outro lado, precisamos de duas pinceladas novas para pintar o arranha-céu $E$ , independentemente de serem reutilizadas depois ou não.

Para o primeiro arranha-céu, sempre precisamos de tantas pinceladas quanto de pisos.

Transformando isso em matemática:

Se anexarmos à lista, isso poderá ser simplificado para:$0$

Comentado

0š¥þO     # expects a list of non-negative integers  e.g. [10, 9, 8, 9]
0š        # prepend 0 to the list                    -->  [0, 10, 9, 8, 9]
  ¥       # compute deltas                           -->  [10, -1, -1, 1]
   þ      # keep only values made of decimal digits
          # (i.e. without a minus sign)              -->  ["10", "1"]
    O     # sum                                      -->  11

Python 3 , 37 bytes

lambda a:sum(a)-sum(map(min,a[1:],a))

Experimente online!

_{-5 bytes mudando para Python 3, graças a Sarien}

Python 2 , 47 43 42 bytes

lambda a:sum(a)-sum(map(min,a[1:],a[:-1]))

Experimente online!

Alt:

lambda a:sum(a)-sum(map(min,zip(a[1:],a)))

Experimente online!

Haskell , 32 bytes

(0%)
p%(h:t)=max(h-p)0+h%t
p%_=0

Experimente online!

Uma melhoria na solução de Lynn que rastreia o elemento anterior em pvez de olhar para o próximo elemento. Isso torna o caso base e a chamada recursiva mais curtos em troca da necessidade de chamar (0%).

max(h-p)0pode ter max h p-po mesmo comprimento.

Haskell , 35 bytes

f(a:b:c)=max(a-b)0+f(b:c)
f a=sum a

Experimente online!

A linha 2 poderia ser f[a]=ase eu também não tivesse que lidar com o caso [].

K (oK) , 12 7 bytes

-5 bytes graças a ngn!

Uma porta k (oK) da solução 05AB1E da Arnauld (e a solução JavaScript da tsh):

+/0|-':

Experimente online!

J , 15 bytes

Porta AJ da solução 05AB1E da Arnauld (e solução JavaScript da tsh):

1#.0>./2-~/\0,]

Experimente online!

Minha solução ingênua:

J , 27 bytes

1#.2(1 0-:])\0,@|:@,~1$~"0]

Experimente online!

Haskell , 34 32 bytes

2 bytes aparados por Lynn

g x=sum$max 0<$>zipWith(-)x(0:x)

Experimente online!

Então, para começar, temos zipWith(-). Isso leva duas listas e produz uma nova lista de suas diferenças aos pares. Em seguida, combinamos com xe (0:x). (0:)é uma função que adiciona zero à frente de uma lista e, combinando-a zipWith(-), obtemos as diferenças entre elementos consecutivos dessa lista com um zero na frente. Então nós zeramos todos os negativos (max 0<$>). Isso cria uma nova lista onde cada elemento é o número de novos traçados que devem ser iniciados em cada torre. Para obter o total, basta somar isso sum.

Japonês , 8 bytes

-2 bytes de @Shaggy

mîT Õ¸¸è

Explicação

mîT Õ¸¸è      Full program. Implicit input U
                e.g. U = [2,0,2]
mîT             Map each item X and repeat T(0) X times
                     U = ["00","","00"]
    Õ           Transpose rows with columns
                     U = ["0 0","0 0"]
     ¸¸         Join using space and then split in space
                     U = ["0","0","0","0"]
        è       Return the count of the truthy values

Experimente online!

MATL , 8 bytes

0whd3Y%s

Experimente online!

Praticamente o algoritmo de @ Arnauld. Salvou um byte (obrigado @LuisMendo) ao transmitir, em uint64vez de selecionar )entradas positivas.

Geléia , 5 bytes

Uma porta da minha resposta 05AB1E , que é semelhante à resposta @tsh JS .

ŻI0»S

Experimente online!

Comentado

ŻI0»S    - main link, expecting a list of non-negative integers  e.g. [10, 9, 8, 9]
Ż        - prepend 0                                             -->  [0, 10, 9, 8, 9]
 I       - compute the deltas                                    -->  [10, -1, -1, 1]
  0»     - compute max(0, v) for each term v                     -->  [10, 0, 0, 1]
    S    - sum                                                   -->  11

Japonês , 7 6 bytes

änT fq

Tente

1 byte economizado graças a Oliver.

änT xwT    :Implicit input of integer array
än         :Consecutive differences / Deltas
  T        :  After first prepending 0
    f      :Filter elements by
     q     :  Square root (The square root of a negative being NaN)
           :Implicitly reduce by addition and output

R , 30 bytes

sum(pmax(0,diff(c(0,scan()))))

Experimente online!

Portabilidade da solução @Arnauld, que por sua vez deriva da ótima solução @tsh

Retina 0.8.2 , 21 bytes

\d+
$*
(1+)(?=,\1)

1

Experimente online! O link inclui casos de teste. Explicação:

\d+
$*

Converta para unário.

(1+)(?=,\1)

Exclua todas as sobreposições da próxima torre, que não precisam de um novo golpe.

1

Conte os traços restantes.

Lisp comum, 88 87 bytes

(lambda(s)(let((o 0))(dolist(c s)(incf o(max 0 c))(mapl(lambda(y)(decf(car y)c))s))o))

não minificado

(lambda (skyline)
  (let ((output 0))
    (dolist (current-skyscraper-height skyline)
      (incf output (max 0 current-skyscraper-height))
      (mapl (lambda (skyscraper)
              (decf (car skyscraper) current-skyscraper-height))
            skyline))
    output)))

Teste-o

Quando uma torre é pintada, são necessárias várias pinceladas iguais à sua altura. Essas pinceladas são traduzidas para todas as seguintes, as quais são indicadas aqui subtraindo a altura da torre atual de todas as outras torres (e ela mesma, mas isso não importa). Se uma torre a seguir for mais curta, ela será empurrada para um número negativo, e esse número negativo será subtraído das torres que se seguem (indicando pinceladas que não puderam ser traduzidas de uma torre anterior para as próximas). Na verdade, apenas subtrai o número de todas as alturas da torre, incluindo as anteriores, mas isso não importa, porque não olhamos para as anteriores novamente.

05AB1E , 13 10 bytes

Z>Lε@γPO}O

Experimente online ou verifique todos os casos de teste .

Explicação:

Z            # Get the maximum of the (implicit) input-list
 >           # Increase it by 1 (if the list only contains 0s)
  L          # Create a list in the range [1, max]
   ε         # Map each value to:
    @        #  Check if this value is >= for each value in the (implicit) input
     γ       #  Split into chunks of adjacent equal digits
      P      #  Take the product of each inner list
       O     #  Take the sum
        }O   # And after the map: take the sum (which is output implicitly)

C # (compilador interativo do Visual C #) com sinalizador /u:System.Math, 47 bytes

n=>n.Select((a,i)=>i<1?a:Max(a-n[i-1],0)).Sum()

Experimente online!

Versão antiga, com sinalizador /u:System.Math, 63 bytes

n=>n.Aggregate((0,0),(a,b)=>(a.Item1+Max(0,b-a.Item2),b)).Item1

Eu sinto que esta solução é mais elegante que a primeira. Ele percorre a matriz com uma tupla de dois valores como valor inicial, captando valores e armazenando o valor antes dele na segunda parte da tupla.

Experimente online!

Pitão, 8 bytes

s>#0.++0

Mais um exemplo da maravilhosa resposta de @ tsh . Toma a soma ( s) dos valores positivos ( >#0) dos deltas (. +) Da entrada com 0 prefixado ( +0Q, Q à direita inferido).

Experimente online aqui ou verifique todos os casos de teste de uma vez aqui .

Método de união de cadeias, 10 bytes

Esta foi a solução que escrevi antes de procurar as outras respostas.

lcj.t+d*LN

Suíte de teste.

lcj.t+d*LNQ   Implicit: Q=eval(input()), b=<newline>, N=<quote mark>
              Trailing Q inferred
        L Q   Map each element of Q...
       * N    ... to N repeated that many times
     +b       Prepend a newline
   .t         Transpose, padding with spaces
  j           Join on newlines
 c            Split on whitespace
l             Take the length, implicit print

Clojure, 50 bytes

#((reduce(fn[[s n]i][(+(max(- i n)0)s)i])[0 0]%)0)

Experimente online! (Por que isso não imprime nada?)

#( ; begin anonymous function
    (reduce
        (fn [[s n] i] ; internal anonymous reducing function, destructures accumulator argument into a sum and the previous item
            [(+ (max (- i n) 0) s ; the sum part of the accumulator becomes the previous sum plus the larger of zero and the difference between the current number and the last one, which is how many new strokes need to be started at this point
            i]) ; ...and the previous item part becomes the current item
        [0 0] ; the initial value of the accumulator gives no strokes yet, and nothing for them to cover yet
        %) ; reduce over the argument to the function
    0) ; and get the sum element of the last value of the accumulator.

Java (JDK) , 57 bytes

a->{int s=0,p=0;for(int x:a)s-=(x>p?p:x)-(p=x);return s;}

Experimente online!

Outro porto de TSH 's resposta Javascript . Portanto, verifique se você os votou positivamente.

Observe que eu usei subtração em vez de adição porque me permitiu escrever (p=x)como operando certo na mesma instrução.

MATL , 15 14 13 bytes

ts:<~"@Y'x]vs

Entrada é um vetor de coluna, usando ;como separador.

Experimente online! Ou verifique todos os casos de teste .

Explicação

t       % Implicit input: column vector. Duplicate
s       % Sum
:       % Range from 1 to that. Gives a row vector
<~      % Greater or equal? Element-wise with broadcast
"       % For each column
  @     %   Push current columnn
  Y'    %   Run-length encoding. Gives vector of values (0, 1) and vector of lengths
  x     %   Delete vector of lengths
]       % End
v       % Vertically concatenate. May give an empty array
s       % Sum. Implicit display

Perl 5, 21 bytes

$\+=$_>$'&&$_-$';//}{

TIO

Como

• -p+ }{+ $\truque
• //corresponde à sequência vazia, para que, para a próxima linha, a pós- $'correspondência contenha a linha anterior
• $\+=$_>$'&&$_-$'acumular diferença entre a linha atual e a anterior se a corrente for maior que a anterior (também pode ser escrita $\+=$_-$' if$_>$', mas o perl não analisa $\+=$_-$'if$_>$'o mesmo)

Stax , 8 bytes

Φ┐Γ╟φφ.╨

Execute e depure

Usa a abordagem amplamente usada da solução JavaScript da tsh.

Wolfram Language (Mathematica) , 34 bytes

Uma porta de @Arnauld da solução .

Tr@Select[{##,0}-{0,##},#>0&]&@@#&

Experimente online!