UVa Problem 10154 Weights and Measures (중량 과 힘)

// Weights and Measures （     ）
// PC/UVa IDs: 111103/10154, Popularity: C, Success rate: average Level: 3
// Verdict: Programming Challenges - Solved, UVa - Accepted
// Submission Date: 2011-10-12
// UVa Run Time: 0.080s
//
//     （C）2011，  。metaphysis # yeah dot net
//
// 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.
//
// 			Yertle the Turtle, Dr.Seuss
//
// [Problem Description]
// A turtle named Mack, to avoid being cracked, has enlisted your advice as to
// the order in which turtles should be stacked to form Yertle the Turtle’s throne.
// Each of the 5,607 turtles ordered by Yertle has a different weight and strength.
// Your task is to build the largest stack of turtles possible.
//
// [Input]
// Standard input consists of several lines, each containing a pair of integers
// separated by one or more space 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 300 g with a strength of 1,000 g can carry 700 g of turtles
// on its back. There are at most 5,607 turtles.
//
// [Output]
// Your output is a single integer indicating the maximum number of turtles that
// can be stacked without exceeding the strength of any one.
//
// [Sample Input]
// 300 1000
// 1000 1200
// 200 600
// 100 101
//
// [Sample Output]
// 3
//
// [    ]
//           DP  ，             ，        ，        ，  
// DP          。    Programming Challenges      ，    UVa    WA。 
//    UVa BBS     ，        PC              （ ...）。
//
//                ，        ，                。 
//                     ，         ，     ，       ：
//
// （1）10 50
// （2）100 120
//
//              （1）      ，（2）    ，           1，     
//  （2）  ，（1）  ，        2      。                    
//      ，               。
//
//       ，                ，         ，             
//   ，    ：
//
// （1）10 1000
// （2）20 1000
// （3）30 40
//
//               2，       3，   （3）       。
//
//         ，           ，          ，           i，  1  
// i - 1           i       ，          j，     i          
//       ，      ，         ，         ，          ，   
//        （           ）：
//
// （1）101 101
// （2）100 201
// （3）99 300
// （4）98 301
// （5）5 302
//
//               3，    （2），（3），（4），（5）            4   
//   ，        ？          （2）   ，    （1）     （2） ，   
// （2）        2，          ，（2）                ，    （1）
//          ，            K      ，        ，         ，
//                     ，            。
//
//               ？      ，       ，         W1，S1，W2，S2，
//    S1 <= S2，      ：
//
// W1 S1
// W2 S2
//
//      S1           W2        ，   S1 >= （W1 + W2），    S2 >= S1
//      S2             ，          ，  S2 >= （W1 + W2），    
// S1 >= （W1 + W2），                  。
//
//     ，              i          h          ，   minWeight
// [h][i]，       ：
//
// minWeight[h][i] = min{minWeight[h][i - 1]，minWeight[h - 1][i - 1] + weight[i]}
//
//           ，  minWeight[h - 1][i - 1] + weight[i] <= strength[i]。   ，
//         ，                   ，                  
//                   。             ，            ， 
//       ，      0，      0      ，         0，      1    
//      ，        ，           MAXINT     。        ：
//
// minWeight[0][0] 0
// minWeight[1][0] MAXINT
// minWeight[2][0] MAXINT
//       ...        ...
// minWeight[N][0] MAXINT
//
//             1  ，       1           ，       ， ：
//
// minWeight[1][1] = min{minWeight[1][0]，minWeight[0][0] + weight[1]}
//
//            （        ），          ，minWeight[1][0]      
//    ，minWeight[0][0]        ，         minWeight[1][1]，       
// minWeight[1][1]      ，         1，     0           ，     
//        ，      ：
//
// minWeight[0] minWeight[1] minWeight[2] ... minWeight[N]
//       0         MAXINT       MAXINT    ...    MAXINT
//
//          ，            ，                        。
//     UVa 10069 Distinct Subsequences               。

#include <iostream>
#include <algorithm>

using namespace std;

#define MAXN 5610
#define MAXINT (1 << 20)

class turtle
{
public:
	int weight;
	int strength;

	bool operator<(const turtle &other) const
	{
		//         。
		if (strength != other.strength)
			return strength < other.strength;

		//      ，        。
		return weight < other.weight;
	};
};

int main(int ac, char *av[])
{
	turtle turtles[MAXN];
	int minWeight[MAXN];
	int nTurtles = 1, weight, strength;
	
	while (cin >> weight >> strength)
	{
		if (weight > strength)
			continue;

		turtles[nTurtles++] = (turtle){weight, strength};
	}

	//           。
	sort(turtles + 1, turtles + nTurtles);
	nTurtles--;

	//    ，   MAXINT           h     。
	minWeight[0] = 0;
	for (int h = 1; h <= nTurtles; h++)
		minWeight[h] = MAXINT;

	// DP      。
	int answer = 1;
	for (int i = 1; i <= nTurtles; i++)
		for (int h = nTurtles; h >= 1; h--)
		{
			if (minWeight[h - 1] + turtles[i].weight <= turtles[i].strength)
			minWeight[h] = min(minWeight[h], minWeight[h - 1] + turtles[i].weight);

			if (minWeight[h] < MAXINT)
				answer = max(answer, h);
		
		}

	cout << answer << endl;

	return 0;
}