题目链接：传送门
题目大意：
总共有N盏灯，老张从点C（1 ≤ C ≤ N）开始关灯（关灯不需要等待时间，C点的灯直接关掉），与此同时灯开始烧电（已知功率Pi）。
老张每次可以往左走关最近的灯或者往右走关掉最近的灯，耗时等于距离。问最少的烧电量。
1 ≤ N ≤ 50。
思路：
状态：
f[i][j]表示在已经关掉i，i+1，…，j的灯时已经浪费的电量。
讨论发现如果要转移状态，还需要加一维表示老站当前的位置：
f[i][j][0]表示老张在位置i，f[i][j][1]表示老张在位置j；
初始状态：
f[C][C][0] = f[C][C][1] = 0；
老张一开始可以直接关掉C点的灯。
状态访问顺序：
更新f[i][j]的时候需要知道f[i+1][j]和f[i][j-1]的状态。
也就是说从C点开始向两边访问即可。
状态转移方程：
f[i][j][0] = max(f[i+1][j][0] + 从点i+1走到点i所花费的时间 * 还没关掉的灯的总功率，
f[i+1][j][1] + 从点j走到点i所花费的时间 * 还没关掉的灯的总功率)
f[i][j][1] = max(f[i][j-1][0] + 从点i走到点j所花费的时间 * 还没关掉的灯的总功率，
f[i][j-1][1] + 从点j-1走到点j所花费的时间 * 还没关掉的灯的总功率)
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int MAX_N = ;
const ll INF = 0x3f3f3f3f3f3f3f3f; int N, C;
int pos[MAX_N];
ll P[MAX_N], sum[MAX_N], f[MAX_N][MAX_N][];// 0 表示停在左端，1 表示停在右端 void dp()
{
for (int i = C; i >= ; i--) {
for (int j = C; j <= N; j++) {
if (i == C && j == C) {
f[i][j][] = f[i][j][] = ;
continue;
}
// (i+1, j) -> (i, j)
if (i+ <= C) {
if (f[i][j][] > f[i+][j][] + (pos[i+] - pos[i]) * (sum[N] - sum[j] + sum[i])) {
f[i][j][] = f[i+][j][] + (pos[i+] - pos[i]) * (sum[N] - sum[j] + sum[i]);
}
if (f[i][j][] > f[i+][j][] + (pos[j] - pos[i]) * (sum[N] - sum[j] + sum[i])) {
f[i][j][] = f[i+][j][] + (pos[j] - pos[i]) * (sum[N] - sum[j] + sum[i]);
}
}
// (i, j-1) -> (i, j)
if (j- >= C) {
if (f[i][j][] > f[i][j-][] + (pos[j] - pos[i]) * (sum[N] - sum[j-] + sum[i-])) {
f[i][j][] = f[i][j-][] + (pos[j] - pos[i]) * (sum[N] - sum[j-] + sum[i-]);
}
if (f[i][j][] > f[i][j-][] + (pos[j] - pos[j-]) * (sum[N] - sum[j-] + sum[i-])) {
f[i][j][] = f[i][j-][] + (pos[j] - pos[j-]) * (sum[N] - sum[j-] + sum[i-]);
}
}
}
}
cout << min(f[][N][], f[][N][]) << endl;
return;
} int main()
{
cin >> N >> C;
sum[] = ;
for (int i = ; i <= N; i++) {
scanf("%d%lld", pos+i, P+i);
sum[i] = sum[i-] + P[i];
}
for (int i = C; i >= ; i--) {
for (int j = C; j <= N; j++) {
f[i][j][] = f[i][j][] = INF;
}
}
dp();
return ;
}
/*
4 3
2 10000
3 10
4 100
5 200 4 3
2 10000
3 200
4 100
5 10
*/