题目：关路灯
网址：https://www.luogu.com.cn/problem/P1220
题目描述
某一村庄在一条路线上安装了 n 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为 1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
输入格式
第一行是两个数字 n（表示路灯的总数）和 c（老张所处位置的路灯号）；
接下来 n 行，每行两个数据，表示第 1 盏到第 n 盏路灯的位置和功率。数据保证路灯位置单调递增。
输出格式
一个数据，即最少的功耗（单位：J，1J=1W×s）。
输入输出样例
输入
5 3
2 10
3 20
5 20
6 30
8 10
输出
270
说明/提示
样例解释
此时关灯顺序为** 3 4 2 1 5 **。
数据范围
1≤n≤50， 1≤c≤n。
明确一点：老张关的路灯号一定是连续的（也就是说，不会存在“三过路灯不顾”的情况）；证明显然。
我们来定义状态：对于老张，我们先确定当前处于的路灯位置，记作dp[pos]，这样会有显式的问题，因为dp[pos]是从哪个状态转移得到的，不知道！因此，我们还需要确定已经处理过的路灯的范围[L, R]，于是我们可以定义状态：dp[L, R, pos]；不过留意一点，pos指的是当前正关的路灯号，由此可得对于已操作完成的区间[L, R]（包含当前位置），pos = L 或 R。
所以，pos这一维是冗余的，取而代之的是用0/1来表示当前处于位置的左右（1表示在R + 1处，0表示在L - 1处）；而所算的代价恰恰是剩余灯泡的电功率乘以此次移动的时间。
有方程：
dp[i, j, 0] = min{dp[i + 1, j, 0] + (pos[i + 1] - pos[i]) * (sum{p[k] | 1 <= k <= i} + sum{p[k] | j + 1 <= k <= n})， dp[i + 1, j, 1] + (pos[j] - pos[i]) * (sum{p[k] | 1 <= k <= i} + sum{p[k] | j + 1 <= k <= n})}
dp[i, j, 1] = min{dp[i, j - 1, 1] + (pos[j] - pos[j - 1]) * (sum{p[k] | 1 <= k < i} + sum{p[k] | j <= k <= n})， dp[i, j - 1, 0] + (pos[j] - p[i]) * (sum{p[k] | 1 <= k < i} + sum{p[k] | j <= k <= n})}；
阶段为区间长度，决策是它的两个来源：原区间的左侧及右侧。
dp[c, c] = 0，其余正无穷。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 50 + 1;
int n, c, p[maxn], loc[maxn], sum_front[maxn] = {}, sum_back[maxn] = {};
int dp[maxn][maxn][2];
int main()
{
scanf("%d %d", &n, &c);
for(int i = 1; i <= n; ++ i)
{
scanf("%d %d", &loc[i], &p[i]);
}
for(int i = 1; i <= n; ++ i)
{
sum_front[i] = sum_front[i - 1] + p[i];
}
for(int i = n; i > 0; -- i)
{
sum_back[i] = sum_back[i + 1] + p[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[c][c][0] = dp[c][c][1] = 0;
for(int k = 2; k <= n; ++ k)
{
int L, R;
for(L = 1; L <= n - k + 1; ++ L)
{
R = L + k - 1;
dp[L][R][0] = min(dp[L + 1][R][0] + (loc[L + 1] - loc[L]) * (sum_front[L] + sum_back[R + 1]), dp[L + 1][R][1] + (loc[R] - loc[L]) * (sum_front[L] + sum_back[R + 1]));
dp[L][R][1] = min(dp[L][R - 1][0] + (loc[R] - loc[L]) * (sum_front[L - 1] + sum_back[R]), dp[L][R - 1][1] + (loc[R] - loc[R - 1]) * (sum_front[L - 1] + sum_back[R]));
}
}
printf("%d
", min(dp[1][n][0], dp[1][n][1]));
return 0;
}