题解 P1220 【关路灯 】

· · 题解

P1220 关路灯 题解

Part 1：稍微对某一些评论做下解释

1. 求前缀和以及查询的一些相关问题

  inline int count(int l, int r, int i, int j) {
      return (sum[l] + sum[n] - sum[r - 1]) * (d[j] - d[i]);
  }

问：这里为什么是 r-1 呢？

答：我们来模拟一下前缀和就清楚了：

设S_5=a_1+a_2+a_3+a_4+a_5 S_1=a_1 S_2=a_1+a_2

那么a_2-a_5的和=? 不难发现，其值=S_5-S_1，这就是为什么是r-1的原因了。

如果从理论上分析：因为S_i包含了从1到i的前缀和，而i到k(k>=i)的和是要包括a_i的，但是S_k-S_i却没有包括a_i，所以就是这么写。

2. 为什么要给f数组赋一个极大值和赋值的一些相关问题

问1：为什么赋最大值：这个是显而易见的，因为我们的dp过程求的是最小值，而这个最小值很明显是大于0的，而f数组的初值是0，所以不小心我们就会取到这个0(大概是这样吧，这个问题有点浅显)

问2：

  memset(f,127,sizeof(f);

这句话什么意思？

那这里**127对应的就是极大值**了，当然我用的是**0x3f** ----------------以上是对我看到的问题的解答---------------- ------------ Part 2：问题解答完毕，思路还是要讲的 ------------ 题目很明显，我们**定义**： 1. $f[i][j][0]$表示从$i-j$耗费的最小电力并且当前站在$i$处； 1. $f[i][j][1]$表示从$i-j$耗费的最小电力并且当前站在$j$处； **目标状态**：$min(f[1][n][0],f[1][n][1])

这不就很明确了吗？

我们知道起点c，那我们由c开始向两边走就行了，向右是正向的，所以向右的状态需要正序搜索，f[l][r]是由上一步f[l][r-1]转移来的，转移方程：

  k1 = f[l][r - 1][0] + count(l - 1, r, l, r);
  k2 = f[l][r - 1][1] + count(l - 1, r, r - 1, r);
  f[l][r][1] = std::min(k1, k2);
  //k1 k2 只是为了让代码不那么长，count函数上文写了;

向左就是反向，倒序搜索，f[l][r]是由f[l+1][r]转移来的，转移方程：

  k1 = f[l + 1][r][0] + count(l, r + 1, l, l + 1);
  k2 = f[l + 1][r][1] + count(l, r + 1, l, r);
  f[l][r][0] = std::min(k1, k2);

思路到此为止，到这里就足够AC了。

part 3：下面是Show Time

自从观摩了某篇std后码风大变（源于对Dalao的崇拜）

思路上面讲的很清楚了，下面代码就不再赘述了

#include<bits/stdc++.h>

template <class T>
inline void read(T &x) {
    static char c;
    static bool op;
    while(!isdigit(c = getchar()) && c != '-');
    x = (op = c == '-')? 0 : c - '0';
    while(isdigit(c = getchar()))
        x = x * 10 + c - '0';
    if(op) x = ~x + 1;
}

template <class T>
void putint(T x) {
    static char buf[15], *tail = buf;
    if(!x) putchar('0');
    else {
        if(x < 0) putchar('-'), x = ~x + 1;
        for(; x; x /= 10) *++tail = x % 10 + '0';
        for(; tail != buf; --tail) putchar(*tail);
    }
    putchar('\n');
}

const int N = 55;
int n, c, ans;

namespace DP {
    static int d[N],sum[N];
    static int f[N][N][2];
    void in() {
        std::memset(sum, 0, sizeof(sum));
        read(n), read(c); 
        for(int i = 1; i <= n; ++i) {
            read(d[i]), read(sum[i]);
            sum[i] += sum[i - 1];
        }
    }
    inline int count(int l, int r, int i, int j) {
        return (sum[l] + sum[n] - sum[r - 1]) * (d[j] - d[i]);
    } 
    void solve(int &ans) {
        std::memset(f, 0x3f, sizeof(f));   
        f[c][c][0] = f[c][c][1] = 0;

        for(int r = c; r <= n; ++r) {
            for(int l = r - 1; l; --l) {
                int k1, k2;

                k1 = f[l + 1][r][0] + count(l, r + 1, l, l + 1);
                k2 = f[l + 1][r][1] + count(l, r + 1, l, r);
                f[l][r][0] = std::min(k1, k2);

                k1 = f[l][r - 1][0] + count(l - 1, r, l, r);
                k2 = f[l][r - 1][1] + count(l - 1, r, r - 1, r);
                f[l][r][1] = std::min(k1, k2);
            }
        }
        ans = std::min(f[1][n][1], f[1][n][0]);
    }
} 

using DP::in;
using DP::solve;

int main() {
    in();
    solve(ans);
    putint(ans);
    return 0;
}

End

走过路过点个赞呗QAQ