UVA 10154 Weights and Measures

//  乌龟塔问题：每个乌龟有力量和重量，求最多能堆多少乌龟？
//  注：乌龟的力量表示背上能承受的重量(包括自己的重量)

//  [解题方法]
//  对乌龟数组按力量S从小到大sort(若S一样，无所谓)
//  堆的时候是后面的乌龟堆在下面
//  为什么这样sort得到的结果最好？
//  原因：对于乌龟a和乌龟b，设as<bs，
//      若a能背b，则as>=aw+bw，那么必有：bs>aw+bw，即b能背a
//      反之，若b能背a, a就不一定能背b了
//      所以得：b更能背，所以b放后面

//  dp[i]表示堆i个乌龟的最小重量(若为-1，则表示不可能堆i个乌龟)
//  状态转移：
//  dp[j](n>=j>=1) = min(dp[j], dp[j-1]+W[i]|S[i]>=dp[j-1]+W[i])
//      dp[j-1]+w[i]表示：将i乌龟放到最底，背上dp[j-1]的量

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define M 5700

struct point{
	int w, s;
}p[M];

int dp[M];

bool cmp (point a, point b)
{
	return a.s < b.s;
}

int main()
{
	int n = 1, i, j, maxs = 0;
	while (cin >> p[n].w >> p[n].s)
		n++;
	--n;
	sort (p+1, p+n+1, cmp);
	memset (dp, -1, sizeof(dp));
	dp[0] = 0;
	for (i = 1; i <= n; i++)
	{
		for (j = n; j >= 1; j--)
		{
			if (dp[j-1] < 0) continue;
			if (dp[j-1] + p[i].w <= p[i].s &&
                (dp[j] < 0 || dp[j] > dp[j-1] + p[i].w))
			{
				dp[j] = dp[j-1] + p[i].w;
				if (j > maxs) maxs = j;
			}
		}
	}
	cout << maxs << endl;
    return 0;
}