WPC4F - Through the troops


Having crossed the first hurdle, Mario encounters a long and narrow alleyway, with turtles. Mario can cross it by jumping from one turtle to another. Whenever Mario makes his jump on any given turtle, he can leave it in any of the three possible states, as per his choice. These states are:

  • Active (A)
  • Dormant (D)
  • Bruised (B)

There are n turtles in the street, indexed 0..(n-1). Each jump costs some amount of energy, which depends on the index of turtle as well as the state it is left in. However, Mario has to take care that no neighboring turtles are left in the same state, or otherwise they all will reunite and cause a fatal attack on Mario, as he is about to leave the alley.

The neighbors of turtle i are turtles i-1 and i+1. (Edited: If n >= 3,) The first and last turtles are not neighbors.

You need to find out the minimum amount of energy required to cross the alley.

Input

first line contains no. of test cases T (T <= 5)
T input sets are given in the following manner:

  • the first line contains n, no. of turtles (n <= 20)
  • the next n lines have space separated 3 numbers (a1, a2, a3), the values of energy needed for ith turtle to change into states A D B (0 <= ai <= 1000)
  • similarly, the inputs are given for other cases

Output

T lines, the minimal energy needed for each set of input

Example

Input:
2
3
0 1 2
1 4 8
9 2 5
4
10 10 10
2 4 9
12 7 10
6 6 6

Output:
4
25

hide comments
shubham9466: 2016-09-06 20:53:34

Easy Dp!! Nice to start with :-)

geeta: 2016-07-04 14:59:09

green bar in one go!!!

poojan : 2016-05-09 07:39:58

easiest dp i ever solve!

anshal dwivedi: 2016-01-08 05:55:06

Cakewalk!

priyank: 2015-10-05 19:36:12

Take care of Whitespace in input. It cause me 1 NZEC error

Dushyant Singh: 2015-09-24 15:12:54

Weak test cases!
Input
1
2
1 2 3
1 2 3
Output should be 2 but my program which gave output as 3 also got accepted. First answer(2) for above test case is correct because according to problem statement "The first and last turtles are not neighbors." so which means for n=2 we can leave both turtles in same state!

Last edit: 2015-09-24 15:13:33
SangKuan: 2015-08-18 00:29:18

easy dp

kp: 2015-06-28 05:30:06

50th

r0bo_dart: 2015-06-26 11:53:01

@Walrus please ensure that all your variable limits hold true in your test cases as well. It is mentioned that 0<ai<=1000 but then it is certainly not the case as the code failed for
# define inf 1000 #define inf 10000
and PASSED for #define inf 100000,

Costed me 2WA's for absolutely no reason.
Hint: DP

#include: 2015-01-26 12:32:39

AC in 1 go
thanks @Ouditchya Sinha


Added by:Walrus
Date:2011-10-24
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local Contest: WPC 4