Tävlingsprogrammering/Uppgifter/Dansmatta

Lösning

Problemet kan lösas med hjälp av Dynamisk programmering. Vi låter DP-tillståndet innehålla två parameterar: var vi har våra två fötter just nu, och vilken ruta vars krav vi ska uppfylla härnäst. Den viktiga insikten är att oavsett vad som hänt "tidigare i en lösning" så kan vi alltid formulera en rekursiv lösning som bara beror på de två parametrarna. Det betyder sedan att vi bara behöver beräkna svaret för varje tillstånd en gång, dvs vi kan i vår rekursiva funktion helt enkelt kolla om vi beräknat svaret för nuvarande state tidigare, och i så fall vad det var. Antal kombinationer för var vi kan ha våra fötter är (4 välj 2) = 6, och max-indexet är 1000. Alltså har vi maximalt 6 * 1000 olika tillstånd.

Lite mer komplex lösning i Python av Oskar Werkelin Ahlin:

from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(100000) # lol

def popcount(x): # returnerar antalet ettsatta bitar i ett tal
    return bin(x).count('1')

vals = {}

# definierar lite konstanter för var vi kan ha fötterna
vals['V'] = 1<<0
vals['U'] = 1<<1
vals['H'] = 1<<2
vals['N'] = 1<<3

N = int(stdin.readline())
reqs = []

# översätt indatasträngarna till heltal på samma format som ovan
for i in xrange(N):
    cur = 0
    for c in stdin.readline():
        for key in vals:
            if c == key:
                cur = cur | vals[key]
    reqs.append(cur)

memory = {}

def solve(feet, index):
    if (feet, index) in memory: # har vi varit här förut?
        return memory[(feet,index)]
    if index == len(reqs): # är vi klara? då behöver vi inte flytta något mer, returnera 0.
        return 0
    minv = 1<<30
    for b in [12, 10, 9, 6, 5, 3]: # möjliga bitkombinationer för fotpositionerna
        if popcount(b) != 2:
            continue
        if b & reqs[index] == reqs[index]:
            minv = min(minv, popcount(feet ^ b)/2 + solve(b, index+1)) # vi letar efter minimum, anropa rekursivt
    memory[(feet,index)] = minv # spara nu värdet i tabellen så vi slipper räkna om det
    return minv

# skriv ut svaret för det första tillståndet vi når: att vi flyttar fötterna för att uppfylla 
# den första rutans krav, och att vi har fötterna på H och V rutor.
print solve(vals['V'] | vals['H'], 0)