由于入队时只有队列元素个数>=2时会有元素弹出,所以先比较斜率再比较转移段数并不能保证斜率相同的情况下队头的转移段数最多,还应该跟队里第二个元素比较。 以下代码求出的最大段数并不正确:
dp[i][0] = f(q[hh]) + pw(s[i]) + 2 * s[i] - 2 * s[i] * s[q[hh]];
dp[i][1] = dp[q[hh]][1] + 1;
正确的转移应该是:
if (hh == tt){
dp[i][0] = f(q[hh]) + pw(s[i]) + 2 * s[i] - 2 * s[i] * s[q[hh]];
dp[i][1] = dp[q[hh]][1] + 1;
}
else {
if (f(q[hh]) - 2 * s[i] * s[q[hh]] < f(q[hh + 1]) - 2 * s[i] * s[q[hh + 1]]) {
dp[i][0] = f(q[hh]) + pw(s[i]) + 2 * s[i] - 2 * s[i] * s[q[hh]];
dp[i][1] = dp[q[hh]][1] + 1;
}
else if (f(q[hh]) - 2 * s[i] * s[q[hh]] > f(q[hh + 1]) - 2 * s[i] * s[q[hh + 1]]) {
dp[i][0] = f(q[hh + 1]) + pw(s[i]) + 2 * s[i] - 2 * s[i] * s[q[hh + 1]];
dp[i][1] = dp[q[hh + 1]][1] + 1;
}
else {
dp[i][0] = f(q[hh]) + pw(s[i]) + 2 * s[i] - 2 * s[i] * s[q[hh]];
dp[i][1] = std::max(dp[q[hh]][1], dp[q[hh + 1]][1]) + 1;
}
}