传送门
如果去关某一个灯，那么途中经过的灯都能关闭，那么就是连续一段区间，区间DP。
f[i][j][0] 表示关完 i, j 这个区间且在 i 这个位置
f[i][j][1] 表示关完 i, j 这个区间且在 j 这个位置
代码
#include <cstdio> #include <cstring> #include <iostream> #define N 1001 #define min(x, y) ((x) < (y) ? (x) : (y)) int n, s; int f[N][N][2], a[N], d[N]; inline int read() int main() printf("%d\n", min(f[1][n][0], f[1][n][1])); return 0; }
上一篇：[luoguP1015] 回文数（模拟 + 高精度？）
下一篇：[luoguP1033] 自由落体（模拟？）
DP
