关于斜率优化dp求最大段数
  • 板块P4983 忘情
  • 楼主ac_de_taffy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/14 13:28
  • 上次更新2024/8/14 15:17:33
查看原帖
关于斜率优化dp求最大段数
1044960
ac_de_taffy楼主2024/8/14 13:28

由于入队时只有队列元素个数>=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;
                }
            }
2024/8/14 13:28
加载中...