[luoguP1220] 关路灯（DP）

传送门

如果去关某一个灯，那么途中经过的灯都能关闭，那么就是连续一段区间，区间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; }

　　

上一篇：[luoguP1056] 排座椅（sort + 模拟）

下一篇：[luoguP1922] 女仆咖啡厅桌游吧（奇奇怪怪的树形DP）

---

DP