悦动达人
Description
一个游戏，在屏幕上有5个格子形成一行，每一秒都会有一个格子闪烁，格子闪烁时你需要保证至少有一只手指在格子上面， 现在我们已经知道第i秒时，第xi个格子会闪烁，我们假设手指的移动不花费时间，你现在用两根手指玩这个游戏， 设初始两根手指都在0处位置，算出n秒过后手指需要移动的最小距离。（允许手指交叉）
注：手指移动的距离的计算是，假设你的一根从x，移动到y格，那么移动的距离是|x-y|
Input
第一行一个数T，表示有T组测试数据（T<=50） 第二行，n，表示进行n秒(1<=n<=10^4) 下一行 n个数，xi（0<=xi<=4）
Output
输出n秒过后手指需要移动的最小距离.
Sample Input
1 2 0 2
Sample Output
2
HINT
#include<stdio.h>
#include<string.h>
#include<math.h>
const int inf = 0x3f3f3f3f ;
int T ;
int n ;
int x ;
int a[ + ][][] ; void init ()
{
for (int i = ; i <= n ; i++ ) {
for (int j = ; j < ; j++ ) {
for (int k = ; k < ; k++ ) {
a[i][j][k] = inf ;
}
}
}
a[][][] = ;
} int solve ()
{
int x ;
for (int i = ; i <= n ; i++) {
scanf ("%d" , &x ) ;
for (int j = ; j < ; j++ ) {
for (int k = ; k < ; k++ ) {
a[i][j][k] = a[i - ][j][k] ;
// printf ("%-10d " , a[i][j][k]) ;
}
// puts ("") ;
}
// puts ("") ;
for (int j = ; j < ; j++ ) {
for (int k = ; k < ; k++ ) {
if (a[i - ][j][k] + fabs (j - x) < a[i][x][k]) {
a[i][x][k] = a[i - ][j][k] + fabs (j - x) ;
}
if (a[i - ][j][k] + fabs (k - x) < a[i][j][x]) {
a[i][j][x] = a[i - ][j][k] + fabs (k - x) ;
}
if (j - x != && k - x != ) {
a[i][j][k] = inf ;
}
}
}
}
/* for (int i = 0 ; i < 5 ; i++) {
for (int j = 0 ; j < 5 ; j++) {
printf ("%-10d " , a[n][i][j]) ;
}
puts ("") ;
}
puts ("") ; */
} int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
scanf ("%d" , &T ) ;
while (T--) {
scanf ("%d" , &n ) ;
init () ;
solve () ;
int minn = inf ;
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
if (a[n][i][j] < minn) {
minn = a[n][i][j] ;
}
}
}
printf ("%d\n" , minn ) ;
}
return ;
}
第一道手刃的多维dp。
一开始还以为这倒也可以用省空间的写法写，但果断orz
总体来说写的蛮顺利。