【题意】：一只手，相对拇指不动，至少要占5个位置，至多可以弹9个键。拇指移动距离x需要花费floor(sqrt(x)),已知左右手的初始位置和接下来要弹奏的n个键，求弹完n个键的最小花费。
【题解】：比较明显的dp。
设dp[k][i][j]表示已经弹完k个键，左手在i，右手在j的最小花费。
思考一下，对于每一次弹的键来说，我们最多移动一只手，既不会同时移动两只手，显然两只手都移动肯定不是最优情况，所以不需要考虑。
对于一些没用状态，既弹不到当前的键，直接设为inf。
总的来说就是，这题无用状态很多，我们只需要处理有用的状态。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 using namespace std;
12 #define pb push_back
13 #define lc(x) (x << 1)
14 #define rc(x) (x << 1 | 1)
15 #define lowbit(x) (x & (-x))
16 #define ll long long
17 #define maxn 1050
18 #define maxm 52
19 const int inf = 1 << 30;
20 const int gap = 9;
21 int dp[maxn][maxm][maxm];
22 int l, r, n, key;
23 int isqrt[100];
24
25 void init() {
26 //抄了watashi的平方根预处理，写得太漂亮了
27 for(int i = 0; i < 10; i++)
28 for(int j = i * i; j < (i + 1) * (i + 1); j++)
29 isqrt[j] = i;
30 }
31
32 int main() {
33 while(~scanf("%d%d%d", &l, &r, &n)) {
34 init();
35 for(int k = 0; k < maxn; k++)
36 for(int i = 0; i < maxm; i++)
37 for(int j = 0; j < maxm; j++)
38 dp[k][i][j] = inf;
39 dp[0][l][r] = 0;
40 for(int now = 0; now < n; now++) {
41 scanf("%d", &key);
42 for(int i = 0; i < maxm; i++) {
43 for(int j = 0; j < maxm; j++) {
44 if(dp[now][i][j] == inf) continue;
45 for(int k = key; k - key < gap && k < maxm; k++)
46 dp[now+1][k][j] = min(dp[now+1][k][j], dp[now][i][j] + isqrt[abs(i-k)]);
47 for(int k = key; key - k < gap && k >= 0; k--)
48 dp[now+1][i][k] = min(dp[now+1][i][k], dp[now][i][j] + isqrt[abs(j-k)]);
49 }
50 }
51 }
52 int ans = inf;
53 for(int i = 0; i < maxm; i++)
54 for(int j = 0; j < maxm; j++)
55 ans = min(dp[n][i][j], ans);
56 printf("%d\n", ans);
57 }
58 return 0;
59 }
60