小白dp uva 10154 - Weights and Measures (贪心+dp )
小白dp uva 10154 - Weights and Measures (贪心+dp )
Problem F: Weights and Measures
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.
The Problem
Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle's throne. Each of the five thousand, six hundred and seven 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 300g with a strength of 1000g could carry 700g 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.
Sample Input
300 1000 1000 1200 200 600 100 101Sample Output
3
题意: 给出n个乌龟的重量w和承载量s,让你用其中一些乌龟堆出一个高度最大的stack来。 n<5607,w、s范围未给。
思路: 贪心分析知s-w小的需在前面,先按s-w排序,然后dp。 dp[i][j] -- 第i个乌龟堆出第j层所需的最小重量。 那么有 dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+w[i]); 前提 i 能承载
感想: 开始想状态总想着有一维与重量相关什么的,每到一个状态既要保证高度大,又要保证重量小,感觉好困难的样子,思路受阻,还是看了题解怎样找的状态,状态知道后立马就知道怎么做了 = =。 其实题目给出的数据范围、或未给的来推测能暗示你怎样建状态的,朝不看题解继续努力!
代码:
#include#include #include #include #include #include #include
用户评论