[luoguP1103] 书本整理（DP）

传送门

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

去掉 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

上一篇：[luoguP2904] [USACO08MAR]跨河River Crossing（DP）

下一篇：[luoguP2031] 脑力达人之分割字串（DP）

---

DP