洛谷 P1103 书本整理

题目传送门

解题思路：

f[i][j]表示前i本书留下j本书的最佳答案(第i本也留下).

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 
 7 using namespace std;
 8 
 9 int n,k,f[201][201],sum,ans;
10 struct kkk{
11     int a,b;
12 }e[101];
13 
14 inline bool cmp(kkk x,kkk y) {
15     return x.a <= y.a;
16 }
17 
18 inline int min(int a,int b) {
19     if(a < b) return a;
20     return b;
21 }
22 
23 int main() {
24     scanf("%d%d",&n,&k);
25     memset(f,0x3f3f3f,sizeof(f));
26     for(int i = 1;i <= n; i++)
27         scanf("%d%d",&e[i].a,&e[i].b);
28     sort(e+1,e+1+n,cmp);
29     for(int i = 1;i <= n; i++) f[i][1] = 0;
30     ans = 0x3f3f3f;
31     for(int i = 2;i <= n; i++)
32         for(int j = 1;j < i; j++)
33             for(int p = 2;p <= min(i,n - k); p++)
34                 f[i][p] = min(f[j][p-1] + abs(e[i].b - e[j].b),f[i][p]);    
35     for(int i = n - k;i <= n; i++)
36         ans = min(ans,f[i][n-k]);
37     printf("%d",ans);
38     return 0;
39 }