I know, up on top you are seeing great sights,But down at the bottom, we, too, should have rights.We turtles can’t stand it. Our shells will all crack!Besides, we need food. We are starving!” groaned Mack.Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtlesshould be dispatched to form Yertle’s throne. Each of the five thousand, six hundred and seven turtlesordered by Yertle has a different weight and strength. Your task is to build the largest stack of turtlespossible.InputStandard input consists of several lines, each containing a pair of integers separated by one or morespace characters, specifying the weight and strength of a turtle. The weight of the turtle is in grams.The strength, also in grams, is the turtle’s overall carrying capacity, including its own weight. That is,a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. There are atmost 5,607 turtles.OutputYour output is a single integer indicating the maximum number of turtles that can be stacked withoutexceeding the strength of any one.Sample Input300 10001000 1200200 600100 101Sample Output3
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
DP~
n只乌龟，每只有承受重量的上限str（包含自身）和重量wei，求最多能叠多少层。
经典DP，从背包演化而来。
先把乌龟按照承受能力从小到大排序。
然后用f[i][j]表示DP到第i只乌龟，已经有i层的最小总重量，那么f[i][j]=min(f[i-1][j],f[i-1][j-1]+wei[i])，需要判断乌龟i是否能承载所有的重量。
最后最大的使得f[n][i]不为inf的i就是答案。
（输入必须写成我那样，不能直接while……并不知道为什么……）
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int n,f[5610][5610],inf;struct node{ int str,wei;}a[5610];bool Operator < (node u,node v){ return u.str==v.str ? u.wei<v.wei:u.str<v.str;}int main(){ n=1; while(scanf("%d%d",&a[n].wei,&a[n].str)!=EOF) n++;n--; sort(a+1,a+n+1); memset(f,127/3,sizeof(f));inf=f[0][0]; for(int i=0;i<=n;i++) f[i][0]=0; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { f[i][j]=f[i-1][j]; if(a[i].wei+f[i-1][j-1]<=a[i].str && f[i-1][j-1]!=inf) f[i][j]=min(f[i][j],f[i-1][j-1]+a[i].wei); } for(int i=n;i;i--) if(f[n][i]!=inf) { PRintf("%d/n",i);return 0; }}
