关路灯
洛谷题号: P1220
主要算法: 区间 DP
难度: 4.4
https://www.luogu.org/problemnew/show/P1220 https://www.luogu.org/problemnew/show/P1220
思路分析:
发现二维的区间 DP 始终做不了, 因为不知道老王的最后位置在哪儿. 那么既然二维不行, 就增加一位记录位置!
仔细分析发现, 在节省时间的前提下, 关完一个区间的所有灯之后老王一定会在区间的左端点或右端点上.(它不可能关完整个区间以后再中间, 不然它路过的时候干嘛不顺便关掉?). 于是就可以定义 f[i][j][b]表示在关闭区间 i-j 的最小能耗. 其中 b 是个布尔, 若 b==0 代表完成以后老王到了左端点, b==1 代表到了右端点. 这样就考虑了所有情况, 并且答案一定是 Min(f[1][n][0], f[1][n][1]).
考虑如何转移状态. 由于题目要求老王从 c 出发, 所以所有与 c 没有交集的区间都是不可完成的, 直接跳出即可. 所以在区间 dp 枚举区间的时候, 左边界从 c 开始倒着扫, 右边界从 c 开始正着扫就好了. 在这个过程中, 由于对于每一个区间有两个状态左边和右边, 每个状态有两种转移方法, 所以总共四个状态转移方程.
注意这里不用枚举中介值, 因为我们可以通过从前一次的最右边或最左边掉头直接获得最优值.
对于 f[i][j][0]的, 既然关闭完成以后要到达左侧, 有两种选择. 第一种选择关闭完成 f[i+1][j][0]以后往左走一步, 第二种是关闭完 f[i+1][j][1]以后长途跋涉走到最左边. 注意第二种并不是来搞笑的, 对于 f[i+1][j][1]远小于 f[i+1][j][0]时, 这就是很有效的. 那么每一次转移以后需要加上多少的能耗呢? 由于 f[i+1][j]一定已经是关掉了的, 正在消耗的电灯一定是除了 [i+1,j] 以外的所有电灯, 这里弄一个前缀和搞一下就好了. 另外每一秒都会消耗电能, 那么具体消耗了几秒钟就是老王这一次走的距离.
那么对于 f[i][j][1]就很简单了, 一种方法 f[i][j-1][1]然后往右走一步, 或者 f[i][j-1][0]然后一路往右走.
- f[i][j][0] = Min(f[i][j][0], f[i+1][j][0] + (p[i+1]-p[i]) * (sum[i]+sum[n]-sum[j]));
- f[i][j][0] = Min(f[i][j][0], f[i+1][j][1] + (p[j]-p[i]) * (sum[i]+sum[n]-sum[j]));
- f[i][j][1] = Min(f[i][j][1], f[i][j-1][1] + (p[j]-p[j-1]) * (sum[i-1]+sum[n]-sum[j-1]));
- f[i][j][1] = Min(f[i][j][1], f[i][j-1][0] + (p[j]-p[i]) * (sum[i-1]+sum[n]-sum[j-1]));
代码注意点:
- /*This Program is written by QiXingZhi*/
- #include <cstdio>
- #include <cstring>
- #define N (55)
- #define ll long long
- #define INF (0x7f7f7f7f)
- #define read(x) x=Rd()
- #define Max(a,b) (((a)> (b)) ? (a) : (b))
- #define Min(a,b) (((a) <(b)) ? (a) : (b))
- #define FileIn(x) freopen(x".in","r",stdin)
- using namespace std;
- inline int Rd(){
- char c = getchar(); int x = 0;int w = 1;
- while(c ^ '-' && (c < '0' || c> '9')) c=getchar();
- if(c == '-') w = -1, c = getchar();
- while(c>= '0' && c <= '9') x = (x<<3)+(x<<1)+c-48,c = getchar();
- return x * w;
- }
- int n,c;
- int p[N],w[N],sum[N];
- int f[N][N][2];
- int main(){
- // FileIn();
- read(n),read(c);
- memset(f,0x3f,sizeof(f));
- for(int i = 1; i <= n; ++i){
- read(p[i]),read(w[i]);
- sum[i] = sum[i-1] + w[i];
- }
- f[c][c][0] = f[c][c][1] = 0;
- for(int i = c; i> 0; --i){
- for(int j = c; j <= n; ++j){
- if(i>c||j<c)continue;
- f[i][j][0] = Min(f[i][j][0], f[i+1][j][0] + (p[i+1]-p[i]) * (sum[i]+sum[n]-sum[j]));
- f[i][j][0] = Min(f[i][j][0], f[i+1][j][1] + (p[j]-p[i]) * (sum[i]+sum[n]-sum[j]));
- f[i][j][1] = Min(f[i][j][1], f[i][j-1][1] + (p[j]-p[j-1]) * (sum[i-1]+sum[n]-sum[j-1]));
- f[i][j][1] = Min(f[i][j][1], f[i][j-1][0] + (p[j]-p[i]) * (sum[i-1]+sum[n]-sum[j-1]));
- }
- }
- printf("%d", Min(f[1][n][0], f[1][n][1]));
- return 0;
- }
- 2018-05-13 11:35:03
来源: http://www.bubuko.com/infodetail-2648954.html