[LuoguP1220] 关路灯

一道区间 DP

#include<bits/stdc++.h>
using namespace std;
const int N=51;
int n,c;
int w[N],a[N];
int f[N][N][2],s[N];
//f[i,j,0/1] 关 [i,j] 的灯,现在在左 / 右端点的位置
//s 表示功率的前缀和,转移的时候用于累加新消耗的功率
// 目标:min(f[1][n][0],f[1][n][1])
int main(){scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&w[i]),s[i]=s[i-1]+w[i];
    memset(f,0x3f,sizeof(f));
    f[c][c][0]=f[c][c][1]=0;
    for(int k=1;k<=n;k++){for(int i=1;i+k<=n;i++){
            int j=i+k;
            //f[i][j][0]
            f[i][j][0]=min(f[i+1][j][0]+(s[n]-s[j]+s[i])*(a[i+1]-a[i]),
                f[i+1][j][1]+(s[n]-s[j]+s[i])*(a[j]-a[i])
            );
            f[i][j][1]=min(f[i][j-1][0]+(s[n]-s[j-1]+s[i-1])*(a[j]-a[i]),
                f[i][j-1][1]+(s[n]-s[j-1]+s[i-1])*(a[j]-a[j-1])
            );
        }
    }
    printf("%d",min(f[1][n][0],f[1][n][1]));
    return 0;
}

  转载请注明: Sshwy's Blog [LuoguP1220] 关路灯

 上一篇
win10&ubuntu18 双系统 UEFI 安装 win10&ubuntu18 双系统 UEFI 安装
win10&ubuntu18 双系统 UEFI 安装前言安装成功之前倒腾半天,总算没什么损失,搞出来了特此发表 blog,也算是作一个好人吧 条件准备 电脑上已安装的 win10 系统 有网络的环境 (最好在下午 5 点前) ub
2018.10.01
下一篇 
[NOIP2017] 矩阵取数游戏 [NOIP2017] 矩阵取数游戏
本来是很简单的区间 DP 结果还要加一个高精。。。 int128 走起 ```cppincludedefine int __int128using namespace std;const int N=82;int n,m,tot;int
2018.10.01
  目录