题意：给定一个规则问龟兔赛跑的结果，问题在于乌龟在何时选择充电。
解法：由于最多的只有100个充电站，而影响结果的决策发生在各个充电站，因此只要考虑到达充电站时需要采取的策略。通过一个值保留到达某站并充电的最优值即可。
代码如下：
#include <iostream> #include <algorithm> using namespace std; // 如果两个节点连边，那么弧头上的点一定要加油 class Rule { public: static int N; // 充电站的数目 static int vr, vt1, vt2; // 三个速度值 static int efar; // 充电能走的距离 static int eti; // 充电的时间 static int length; // 赛道的长度 }; int Rule::vr, Rule::vt1, Rule::vt2, Rule::N; int Rule::efar, Rule::eti, Rule::length; class Node { private: int x; // 于坐标上的位置 double ti; // 已经花去的时间 bool vis; // 该点是否已经到达过 public: Node() {vis = false;} int getx() const {return x;} double getti() const {return ti;} bool getvis() const {return vis;} void setx(int v) {x = v;} void setti(double v) {ti = v;} void setvis(bool v) {vis = v;} void read() {cin >> x;} // 读取该充电站在轴上的位置 friend double cost(const Node &, const Node &); }; double cost(const Node &a, const Node &b) { int dist = b.getx() - a.getx(); if (dist <= Rule::efar) return Rule::eti + (1.0 * dist / Rule::vt1); else return Rule::eti + (1.0 * Rule::efar / Rule::vt1 + 1.0 * (dist - Rule::efar) / Rule::vt2); } void solve(Node nd[], int MaxN) { for (int i = 0; i <= Rule::N; ++i) { // 枚举从不包括终点的点出发 if (!nd[i].getvis()) continue; // 如果该点还没有更新过，那么其就不去更新其他点 for (int j = i+1; j < MaxN; ++j) { // 从i点出发能够到达的j点就是位于i点后面的点 if (nd[j].getvis()) { // 如果该点已被访问过 nd[j].setti(min(nd[j].getti(), nd[i].getti() + cost(nd[i], nd[j]))); } else { nd[j].setti(nd[i].getti() + cost(nd[i], nd[j])); nd[j].setvis(true); } } } } bool win(Node nd[]) { double a = 1.0 * Rule::length / Rule::vr; double b = nd[Rule::N+1].getti() - Rule::eti; return b < a; } int main() { while (cin >> Rule::length) { cin >> Rule::N >> Rule::efar >> Rule::eti; cin >> Rule::vr >> Rule::vt1 >> Rule::vt2; const int MaxN = Rule::N+2; Node nd[MaxN]; // 对每次数据都调用一次初始化函数 for (int i = 1; i <= Rule::N; ++i) { nd[i].read(); } nd[0].setx(0); // 构造起点和终点 nd[0].setti(0.0); nd[0].setvis(true); nd[Rule::N+1].setx(Rule::length); solve(nd, MaxN); cout << (win(nd) ? "What a pity rabbit!\n" : "Good job,rabbit!\n"); } return 0; }