洛谷 P1220 关路灯（区间dp，前缀和）
生活随笔
收集整理的这篇文章主要介绍了
洛谷 P1220 关路灯（区间dp，前缀和）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
传送门
解题思路
先明确一下题意，c指的是路灯的编号而不是位置。
然后根据贪心，在从点i去关点j的路灯时，所有经过的路灯都会随手关掉（不耗时间），所以我们可以确定，若i点和j点的路灯已经关闭，那么区间i...j的路灯已经全部关闭，而且关完后，最优策略一定是在点i处或者点j处。
这和上一题就很像了，用dp[i][j]表示把区间i...j的路灯全部关闭所有的最小电量。然后dp[i][j][0]表示关完后在i点时的最小电量，dp[i][j][1]表示关完后在j点时的最小电量。
最后想一下动态转移方程，dp[i][j][0]可以从dp[i+1][j][0]和dp[i+1][j][1]转移而来，dp[i][j][1]可以从dp[i][j-1][0]和dp[i][j-1][1]转移而来。
怎样计算呢？很显然是原来的dp值再加上关第i盏灯或第j盏灯要付出的代价。
代价怎么求？
我们很显然能作差求出距离（所用的时间），我们还需要知道到目前为止剩下的还未关的灯的功率和，因为已经关了的灯一定在某一区间内，然后又要求和，所以很自然地就想到了前缀和。
最后的最后，last but not least，重要的事情说三遍：
细节，细节，细节！
AC代码
#include<iostream>
#include<cstring>
using namespace std;
int n,a[],w[],dp[][][],now,sum[];
int main()
{
cin>>n>>now;
memset(dp,0x3f,sizeof(dp));
for(int i=;i<=n;i++){
cin>>a[i]>>w[i];
sum[i]=sum[i-]+w[i];
}
dp[now][now][]=dp[now][now][]=;
for(int len=;len<=n;len++){
for(int i=max(,now-len+);i<=min(now,n);i++){
int j=i+len-;
if(j>n) break;
dp[i][j][]=min(dp[i+][j][]+(sum[i]+sum[n]-sum[j])*(a[i+]-a[i]),dp[i+][j][]+(sum[i]+sum[n]-sum[j])*(a[j]-a[i]));
dp[i][j][]=min(dp[i][j-][]+(sum[i-]+sum[n]-sum[j-])*(a[j]-a[i]),dp[i][j-][]+(sum[i-]+sum[n]-sum[j-])*(a[j]-a[j-]));
}
}
cout<<min(dp[][n][],dp[][n][]);
return ;
}
总结
以上是生活随笔为你收集整理的洛谷 P1220 关路灯（区间dp，前缀和）的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 第八届医学图像计算青年研讨会（MICS
- 下一篇： ORM——Mybatis