Weights and Measures

Weights and Measures

时间: 1ms        内存:256M

描述:

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.

输入:

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.

输出:

Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

示例输入:

300 1000
1000 1200
200 600
100 101

示例输出:

3

提示:

参考答案(内存最优[1852]):

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int f[6000];
struct ab
{
    int w,s;
} a[6000];
bool cmp(ab a,ab b)
{
    return a.s<b.s;
}
int main()
{
    int N=0;
    for(; ~scanf("%d%d",&a[N].w,&a[N].s); N++);
    sort(a,a+N,cmp);
    int M=0,i,j;
    memset(f,INF,sizeof(f));
    f[0]=0;
    for(i=0; i<N; i++)
        for(j=M; j>=0; j--)
        {
            if(a[i].s>=f[j]+a[i].w&&f[j]+a[i].w<f[j+1])
            {
                f[j+1]=f[j]+a[i].w;
                if(j+1>M) M=j+1;
            }
        }
    printf("%d\n",M);
    return 0;
}

参考答案(时间最优[0]):

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 6000
#define INF 1 << 29
#define MIN(a, b) (a < b ? a : b)

struct turtle
{
    int wt, st;
}t[N];

int a[N][N];

int cmp(turtle a, turtle b)
{
    return a.st < b.st;
}

int main()
{
    int n = 1, ans = 1,i,j;
    while(~scanf("%d%d", &t[n].wt, &t[n].st))
    {
        t[n].st -= t[n].wt;
        n++;
    }
    n--;
    for(i = 0; i <= n; i++)
    for(j = 0; j <= n; j++)
        a[i][j] = INF;
    for(i = 0; i <= n; i++)
        a[i][0] = 0;
    sort(t + 1, t + n + 1, cmp);
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= i; j++)
        {
            a[i][j] = a[i - 1][j];
            if(a[i - 1][j - 1] <= t[i].st)
                a[i][j] = MIN(a[i][j], a[i - 1][j - 1] + t[i].wt);
        }
    }
    for(i = n; i; i--)
        if(a[n][i] < INF)
        {
            ans = i;
            break;
        }
    printf("%d\n", ans);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注