这道题隔了一个才做，动归有些生疏了，但从新捡起来发现比以前理解的更透彻了。
f[i]表示托i个乌龟时的最轻重量，不断的去更新重量使其最小。
这里要先做好预处理， 也就是为最长子序列拍好序。但是按照什么顺序排序呢？这里要用到一点贪心，我们想如果现在有两个乌龟，一个力气大一个力气小，重力我们不用管，那么应该把力气大的乌龟放在下面，还是力气小的呢，你可能会想，这和重力有关啊，仔细分析，如果力量大的在下面，力量小的在上面，那么力量大的还能承受的重力就是s[da]-w[xiao]-w[da]，力量小的能够承受的重力为s[xiao]，前者可能大于，等于，或小于后者；如果力量小的在下面，力量大的在上面，那么力量小的能够承受的重力就是s[xiao]-w[xiao]-w[da]，力量大的能够承受的重力为s[da],前者一定小于后者，总的承重能力受制于前者。这两种方式 第二种的总的承重能力显然不及第一种，也就是第一种更优，所以力量大的在下面一定比力量轻的在下面更好。所以我们按力量排序。
因此按照力量升序开始检索，只要满足力量大于本身重力+f[i],就可以更新max及f[i+1],这里更新从大到小是因为我们更新的是f[i+1]，如果从小到大，就破坏的后面的更新。
这里还要提一句，就是力量小于本身体重的，连自己都拖不动，是不会被处理的：
#include<stdio.h> #include<string.h> #include<stdlib.h> #define INF 100000000 #define MAXN 6000 int n, w[MAXN], s[MAXN], f[MAXN], r[MAXN]; int cmp(const void *_p, const void *_q) { int *p = (int *)_p; int *q = (int *)_q; return s[*p] - s[*q]; } void solve() { memset(f, 0x3f, sizeof(f)); f[0] = 0; for(int i = 1; i < n; i ++) r[i] = i; qsort(r+1, n, sizeof(r[0]), cmp); int max = 0; for(int i = 1; i < n; i ++) for(int j = max; j >= 0; j--) if(f[j] + w[r[i]] < s[r[i]] && f[j] + w[r[i]] < f[j+1]) { f[j+1] = f[j] + w[r[i]]; if(j+1 > max) max = j+1; } printf("%d\n",max); } void init() { n = 1; while(~scanf("%d%d",&w[n],&s[n])) if(w[n] <= s[n]) n ++; solve(); } int main() { init(); //system("pause"); return 0; }