思路:
区间dp
首先, 经过分析, 在最优解里, 某个时间被关掉的路灯构成一个区间, 因为如果不是区间, 则可将其变为一段区间, 且得出的解不会更差
用d[i][j][0/1]表示从i到j的区间被关闭, 且老张位于左/右端点的最优解
具体的状态转移看代码
代码:
1 |
|
区间dp
首先, 经过分析, 在最优解里, 某个时间被关掉的路灯构成一个区间, 因为如果不是区间, 则可将其变为一段区间, 且得出的解不会更差
用d[i][j][0/1]表示从i到j的区间被关闭, 且老张位于左/右端点的最优解
具体的状态转移看代码
1 | #include <iostream> |