传送门
以 去掉多少个 为阶段不好做。
去掉 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
上一篇：[POJ3463] Sightseeing（次短路 Heap + Dijkstra）
下一篇：[luoguP2601] [ZJOI2009]对称的正方形（二维Hash + 二分 || Manacher）
DP
