P1103 书本整理

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int hg[300][300];
struct cnt
{
	int h,g;
}add[3000];
bool cmp(cnt a,cnt b)
{
	if(a.h>b.h)
	return 0;
}
int main()
{
	memset(hg,0x3f,sizeof hg);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&add[i].h,&add[i].g);
		hg[1][i]=0;
	}
	sort(add+1,add+1+n,cmp);
	for(int i=1;i<=n-k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=j-1;k>=1;k--)
			{
				hg[i][j]=min(hg[i-1][k]+abs(add[j].g-add[k].g),hg[i][j]);
			}
		}
	}
	long long sum=1e9;
	for(int i=1;i<=n;i++)
	{
		if(sum>hg[n-k][i])
		sum=hg[n-k][i];
	}
	printf("%lld",sum);
	return 0;
}
/*（测试点一数据）
80 40
43 164
9 16
3 200
4 87
5 32
6 85
1 42
27 167
76 129
77 149
23 123
12 123
13 24
35 196
15 19
16 108
17 8
18 140
29 156
70 137
21 58
60 96
56 80
32 64
25 129
22 75
7 142
79 174
10 66
71 66
55 71
68 7
33 106
34 142
78 46
28 132
37 177
73 14
39 58
8 11
41 64
61 146
53 136
52 143
11 190
46 79
50 66
72 166
49 65
75 152
51 55
54 193
44 79
2 150
45 175
48 191
36 16
58 181
59 107
40 187
74 55
62 136
63 175
64 190
65 105
66 67
67 92
30 199
69 5
42 179
24 172
38 58
26 52
14 131
19 105
47 104
20 154
31 30
57 142
80 189
输出：805
*/