首页 > 代码库 > [luoguP1103] 书本整理（DP）
[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 node11 {12 int a, b;13 }p[MAXN];14 15 inline int read()16 {17 int x = 0, f = 1;18 char ch = getchar();19 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;20 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;21 return x * f;22 }23 24 inline bool cmp(node x, node y)25 {26 return x.a < y.a;27 }28 29 inline int min(int x, int y)30 {31 return x < y ? x : y;32 }33 34 inline int abs(int x)35 {36 return x < 0 ? -x : x;37 }38 39 int main()40 {41 int i, j, k;42 n = read();43 m = n - read();44 for(i = 1; i <= n; i++) p[i].a = read(), p[i].b = read();45 std::sort(p + 1, p + n + 1, cmp);46 for(i = 2; i <= n; i++)47 for(j = 2; j <= min(i, m); j++)48 {49 f[i][j] = INF;50 for(k = j - 1; k < i; k++)51 f[i][j] = min(f[i][j], f[k][j - 1] + abs(p[k].b - p[i].b));52 }53 for(i = m; i <= n; i++) ans = min(ans, f[i][m]);54 printf("%d\n", ans);55 return 0;56 }
[luoguP1103] 书本整理（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。