有依赖的背包，正好刚刚学到。
1: #include <stdio.h>
2: #include <stdlib.h>
3: #define maxn 400
4:
5: int f[maxn][maxn];
6: int t[maxn];
7: struct ss
8: {
9: int root,num;
10: } a[maxn];
11: int n,m;
12: int w[maxn];
13:
14: int cmp(const void*a,const void*b)
15: {
16: ss c=*(ss*)a,d=*(ss*)b;
17: if (c.root<d.root) return -1;
18: if (c.root>d.root) return 1;
19: return 0;
20: }
21:
22: void dp(int x)
23: {
24: for (int i=t[x];i<t[x+1];++i)
25: {
26: int k=a[i].num;
27: for (int j=0;j<=m;++j) f[k][j]=f[x][j]+w[k];
28: dp(k);
29: for (int j=1;j<=m;++j)
30: if (f[k][j-1]>f[x][j])
31: f[x][j]=f[k][j-1];
32: }
33: }
34:
35: int main()
36: {
37: scanf("%d%d",&n,&m);
38: for (int i=1;i<=n;++i)
39: {
40: scanf("%d%d",&a[i].root,&w[i]);
41: a[i].num=i;
42: }
43: a[0].root=-1;
44: qsort(a,n+1,sizeof(ss),cmp);
45: for (int i=1;i<=n;++i)
46: if (!t[a[i].root])
47: t[a[i].root]=i;
48: t[n+1]=n+1;
49: for (int i=n;i>=0;--i)
50: if (!t[i])
51: t[i]=t[i+1];
52: dp(0);
53: printf("%d\n",f[0][m]);
54: return 0;
55: }
56: