T2 关路灯
传送门：洛谷P1220
这是一道区间DP的题
关于关灯是没有时间流逝的，当你经过一个灯的时候它就关了，所以当你最后把整个区间的灯关完且所用的电最少你只有可能在 \(1\) 或者是 \(n\) ；
当你关完当前一个灯时，你有两种决策可以得到最优解，一个是继续沿着当前的方向继续走下去关一个功率较小的灯， 另一个是折返回去关一个功率较大的灯；
一道能够用动态规划做的题一定包含了两个特点 : 最优子结构， 重叠子问题；
对于这个题区间 [1, n] 的最优解一定是通过 [2, n] 或 [1, n - 1] 的最优解通过折返或者沿原方向得来的，所以我们定义状态：dp[i][j][0/1] 表示区间 [i, j] 中的所有灯已经关完了工人站在 \(i\) 或 \(j\) 位置的最优解；
状态转移方程式：
dp[i][j][0] = min(dp[i + 1][j][0] + (a[i + 1] - a[i]) * (sum[n] - sum[j] + sum[i]), dp[i + 1][j][1] + (a[j] - a[i]) * (sum[n] - sum[j] + sum[i]));
dp[i][j][1] = min(dp[i][j - 1][0] + (a[j] - a[i]) * (sum[n] - sum[j - 1] + sum[i - 1]), dp[i][j - 1][1] + (a[j] - a[j - 1]) * (sum[n] - sum[j - 1] + sum[i - 1]));
因为不知道最后是站在 \(1\) 还是 \(n\) 最优，ans = min(dp[1][n][0], dp[1][n][1]);
贴代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 50 + 5;
int n, m;
int f[maxn][maxn][2], sum[maxn], a[maxn], c[maxn];
void read() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++ i) {
scanf("%d%d", &a[i], &c[i]);
sum[i] = sum[i - 1] + c[i];
}
memset(f, 0x3f, sizeof f);
f[m][m][0] = f[m][m][1] = 0;
for (int d = 2; d <= n; ++ d) {
for (int i = 1, j; (j = i + d - 1) <= n; ++ i) {
f[i][j][0] = min(f[i + 1][j][0] + (a[i + 1] - a[i]) * (sum[n] - sum[j] + sum[i]), f[i + 1][j][1] + (a[j] - a[i]) * (sum[n] - sum[j] + sum[i]));
f[i][j][1] = min(f[i][j - 1][0] + (a[j] - a[i]) * (sum[n] - sum[j - 1] + sum[i - 1]), f[i][j - 1][1] + (a[j] - a[j - 1]) * (sum[n] - sum[j - 1] + sum[i - 1]));
}
}
printf("%d\n", min(f[1][n][1], f[1][n][0]));
}
int main() {
read();
return 0;
}