2014
03-06

Rocket Stages

Many rockets are made up of several stages to increase efficiency. When the fuel in one stage burns up, the stage can be discarded, reducing the weight of the remaining rocket. The first stage needs a strong engine capable of lifting the whole rocket, while later stages can have smaller engines.

In this problem, you will determine which stages to put together to maximize the upward velocity of the rocket when all the fuel has burned.

For each stage, you will be given:

• the mass S of the stage, in kilograms, when it is empty (without fuel),
• the mass L of the fuel, in kilograms, in the stage,
• the thrust T, in newtons, provided by the engine in the stage, and
• the fuel consumption C, in kilograms per second, of the stage.

Assume that the rocket points straight upward for the duration of the flight. Two forces act on the rocket: the force of the engine, which is T newtons upwards, and the force of gravity, which is 9.8 M newtons downwards, where M is the total mass of the rocket in kilograms, including fuel. The acceleration of the rocket is F divided by M metres per second per second upwards, where F is the total net force acting on the rocket in newtons, and M is the total mass of the rocket in kilograms, including fuel. As soon as a stage finishes burning, it is immediately discarded and the next stage starts to burn. The final velocity of the rocket is the integral of the net acceleration (due to gravity and the engine) over time.

Due to safety regulations, the net acceleration of the rocket is never allowed to be downwards, until the rocket runs out of fuel.

Also due to safety regulations, the total mass of the rocket cannot exceed 10000 kilograms.

The rocket must have at least one stage.

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer N, the number of rocket stages in the current test case. There will be no more than 1000 stages. This line is followed by N lines, one for each stage. Each of these lines contains the four integers S, L, T, C that describe a stage, as explained above. Each of these integers can be represented by a 32-bit unsigned binary number. The order of the stages as listed must be preserved but some stages (including, possibly, the first stage) may be left out of the rocket. The stage listed first is at the top of the rocket (and will burn last). For every test case in the input, it is always possible to construct at least one rocket satisfying all the requirements of the problem statement.

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer N, the number of rocket stages in the current test case. There will be no more than 1000 stages. This line is followed by N lines, one for each stage. Each of these lines contains the four integers S, L, T, C that describe a stage, as explained above. Each of these integers can be represented by a 32-bit unsigned binary number. The order of the stages as listed must be preserved but some stages (including, possibly, the first stage) may be left out of the rocket. The stage listed first is at the top of the rocket (and will burn last). For every test case in the input, it is always possible to construct at least one rocket satisfying all the requirements of the problem statement.

1
1
9999 1 1000000 1

90

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

inline
double solve(double S, double T, double C, double t)
{
return T / C * (-log(S / C - t)) - 9.8 * t;
}

const double E = 1e-12;

inline
int dblcmp(double x)
{
if (x > -E && x < E)
return 0;
return x > 0 ? 1 : -1;
}

struct NN {
long long S, L, T, C;
};

NN aa[1010];
double dp[2][10100];

int main()
{
int cn, cns;

//freopen("input.txt", "r", stdin);

while (scanf("%d", &cns) == 1) {
for (cn = 0; cn < cns; cn++) {
int n;
scanf("%d", &n);
// long long sum[1100];
//sum[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%I64d%I64d%I64d%I64d", &aa[i].S, &aa[i].L, &aa[i].T, &aa[i].C);
//sum[i] = sum[i - 1] + aa[i].s + aa[i].L;
}

for (int j = 0; j <= 10000; j++) {
dp[0][j] = 0;
}
double maxv = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 10000; j++) {
//dp[i][j] = dp[i][j - 1];
int xx = i % 2, yy = (i - 1) % 2;
dp[xx][j] = 0;
dp[xx][j] = max(dp[xx][j], dp[yy][j]);
if (j >= aa[i].S + aa[i].L && (aa[i].T - 9.8 * j) >= 0)
dp[xx][j] = max(dp[xx][j], dp[yy][j - aa[i].S - aa[i].L]
+ solve(j, aa[i].T, aa[i].C, (double)aa[i].L / aa[i].C) - solve(j, aa[i].T, aa[i].C, 0));
if (maxv < dp[xx][j]) {
maxv = dp[xx][j];
}
}

}
printf("%.0lf\n", floor(maxv + 0.5));
}
}
return 0;
}

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。

2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。