这一道题我一直在想时间该怎么算。
看题解发现有个隐藏的贪心。
路径一定是左右扩展的，左右端点最多加+1（我竟然没发现！！）
这个性质非常重要！！
因此这道题用区间dp
f[i][j]表示关完i到j的路灯的消耗。
那么因为要算走的路程，那么还有一维表示当前人在左端点
还是右端点。
然后每次的消耗为当前走这一段的时间乘上这个时候还亮着的路灯
的总功率。
然后这个起点的意义就在于在起点的消耗为0，其他都为正无穷
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1123;
int f[MAXN][MAXN][2], t[MAXN][MAXN];
int w[MAXN], a[MAXN], n, s;int main()
{scanf("%d%d", &n, &s);_for(i, 1, n) scanf("%d%d", &a[i], &w[i]);_for(i, 1, n)_for(j, i, n)t[i][j] = t[i][j-1] + w[j];int sum = t[1][n];_for(i, 1, n)_for(j, i, n)t[i][j] = sum - t[i][j];memset(f, 0x3f, sizeof(f));f[s][s][0] = f[s][s][1] = 0;_for(d, 2, n)_for(i, 1, n){int j = i + d - 1;if(j > n) break;f[i][j][0] = min(f[i+1][j][0] + t[i+1][j] * (a[i+1]-a[i]), f[i+1][j][1] + t[i+1][j] * (a[j]-a[i]));f[i][j][1] = min(f[i][j-1][0] + t[i][j-1] * (a[j]-a[i]), f[i][j-1][1] + t[i][j-1] * (a[j]-a[j-1]));}printf("%d\n", min(f[1][n][0], f[1][n][1]));return 0;
}