【題意】：一只手，相對拇指不動，至少要占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