传送门

以 去掉多少个 为阶段不好做。

去掉 k 个也可以变成选 n k 个

f[i][j] 表示前 i 个数中 选 j 个的最优解，a[i] 必选

f[i][j] = min(f[i][j], f[k][j 1] + abs(b[k] b[i])) (2 <= j <= min(i, n m), j 1 <= k < i)

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 const int MAXN = 101, INF = ~(1 << 31); 7 int n, m, ans = INF; 8 int f[MAXN][MAXN]; 9 10 struct node 11 p[MAXN]; 14 15 inline int read() 16 23 24 inline bool cmp(node x, node y) 25 28 29 inline int min(int x, int y) 30 33 34 inline int abs(int x) 35 38 39 int main() 40 53 for(i = m; i <= n; i++) ans = min(ans, f[i][m]); 54 printf("%d\n", ans); 55 return 0; 56 }
View Code