https://codeforces.com/contest/1065/problem/E

题目很长，大意是一个棋盘N*N，N<=10,每个格子一个[1,N*N]的不同数字

3种棋子:车，马，主教

开局放1个棋子到1号格子

2种操作:变成另一种棋子，或者移动棋子

求1->2->3....->N*N的最小操作数，并求出操作数最小时，最小变换数

 

恶心的模拟题，但是我有一个启发:

使用dp[n][i]表示到达n号格子时状态为i的最小状态(操作数和变换数)

则j∈[0,2],k∈[0,2],表示从n-1号格子的j棋子，使用k棋子跑中间路程

dp[n][i]=min(dp[n][i],

{

calc(point[i-1],point[i],k) + dp[n-1][j].first +(i!=k) + (j!=k) 

,

dp[n-1][j].second+ (i!=k) +(j!=k)

}