- #include <stdio.h>
- #include <stdlib.h>
- const int inf = 1000000000;
- int n;
- int d[128];
- int dp[128][128];
- int Min(int a, int b)
- {
- return a < b ? a : b;
- }
- int main()
- {
- int i, j, k;
- while(scanf("%d", &n) && n)
- {
- for(i = 1; i <= n; i++)
- scanf("%d", d + i);
- for(i = 0; i <= n; i++)
- for(j = 0; j <= n; j++)
- dp[i][j] = inf;
- dp[0][0] = dp[1][0] = 0;
- for(i = 2; i <= n; i++)
- {
- for(j = i - 1; j >= 0; j--)
- dp[i][i - 1] = Min(dp[i][i - 1], dp[i - 1][j] + (j == 0 ? 0 : abs(d[j] - d[i])));
- for(j = 0; j <= i - 1; j++)
- {
- dp[i][j] = Min(dp[i][j], dp[i - 1][j] + abs(d[i] - d[i - 1]));
- }
- }
- int ans = dp[n][0];
- for(i = 1; i <= n; i++)
- {
- ans = Min(ans, dp[n][i] + abs(d[i] - d[n]));
- }
- printf("%d\\n", ans);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/110320132372.html
来源: http://www.codesnippet.cn/detail/110320132372.html