传送门


题意:一个人一开始在一个灯柱那边,每一个灯具有一个功率,他现在要去挨个关灯,问关完所有灯的时候,这些灯泡消耗的最小功率是多少


解答:很明显的区间DP,乍一看感觉类似于P3205 [HNOI2010]合唱队,思路差不多就是看一下老张这个时候在区间的最左边还是最右边,记录一下两种状态对应的答案进行转移,我们使用\(dp[l][r][0]\)表示在区间\([l,r]\)中最终老张停留在左边的情况,同理,\(dp[l][r][1]\)表示在区间\([l,r]\)中最终老张停留在右边的情况。我们让\(getsum(l,r)\)表示区间\([l,r]\)的功率之和,可以使用前缀和预处理出来,那么状态转移方程有

\(dp[l][r][0]=\min(dp[l+1][r][0]+(a[l+1].pos-a[l].pos)*(getsum(1,l)+getsum(r+1,n)),\) \(dp[l+1][r][1]+(a[r].pos-a[l].pos)*(getsum(1,l)+getsum(r+1,n)))\)

 

\(dp[l][r][1]=\min(dp[l][r-1][0]+(a[r].pos-a[l].pos)*(getsum(1,l-1)+getsum(r,n)),\) \(dp[l][r-1][1]+(a[r].pos-a[r-1].pos)*(getsum(1,l-1)+getsum(r,n)))\)

 

分类: DP

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注