109.关路灯（区间dp）

1258 关路灯

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。

多瑞卡每晚到早晨5点钟都在晚会上，然后他开始关灯。开始时，他站在某一盏路灯的旁边。

每盏灯都有一个给定功率的电灯泡，因为多端卡有着自觉的节能意识，他希望在耗能总数最少的情况下将所有的灯关掉。

多端卡因为太累了，所以只能以1m/s的速度行走。关灯不需要花费额外的时间，因为当他通过时就能将灯关掉。

编写程序，计算在给定路灯设置，灯泡功率以及多端卡的起始位置的情况下关掉所有的灯需耗费的最小能量。

输入描述 Input Description

输入文件的第一行包含一个整数N，2≤N≤1000，表示该村庄路灯的数量。

第二行包含一个整数V，1≤V≤N，表示多瑞卡开始关灯的路灯号码。

接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数，其中0≤D≤1000，0≤W≤1000。D表示该路灯与村庄开始处的距离(用米为单位来表示)，W表示灯泡的功率，即在每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。

输出描述 Output Description

输出文件的第一行即唯一的一行应包含一个整数，即消耗能量之和的最小值。注意结果小超过1,000,000,000。

样例输入 Sample Input

2 2

5 8

6 1

8 7

样例输出 Sample Output

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

动态规划区间型DP

分析：

我们发现关掉的路灯一定是连续的 YY易得（= =假装有证明）

然后就想到“ dp[i][j]表示i~j都关掉需要的能源

接着转移转移很蛋疼（或许是我太弱）

首先想到dp[i][j]从dp[i+1][j]或者dp[i][j-1]转移过来这时发现问题了如果不加限制

理论上会出现（以样例为例） dp[4][4]这样不合法的状态而起点在3

那么限制一下端点也很容易搞定

还是有问题= = 这题我写的递归就会递归出在求解dp[2][4]时从dp[3][4]转移过来

也就是说这一步是在4号灯关了的情况下从3走到2 这样对于解的值不好计算于是想到加一个半维

此时dp[i][j][0]表示最后一步落在i dp[i][j][1]表示最后一步落在j

到这里转移基本上很明了了还有个问题在于转移时对增加的能耗的处理

= =一开始我很傻写了个函数用O（n）去算转移时每一秒要耗的能源值

其实这个东西用一个sum[i][j]表示i~j的和就很容易了（况且关了灯的区间又是连续的）

自己的代码：

代码：

#include< cstdio >

#include< iostream >

#include< cstdlib >

#include< cstring >

long long int f[1001][1001][2],sum[1001]={0};

long long int n,d,w,x[1001],v;

using namespace std;

void input()

{

scanf("%d%d",&n,&v);

for(int i=1;i<=n;++i)

{

scanf("%d%d",&d,&w);//d juli w gong lv

sum[i]=sum[i-1]+w;//sum表示前i个灯的功率和，好计算除了区间之外的其他点的消费

x[i]=d;

}

int main()

{

input();

memset(f,0x3f3f3f3f,sizeof(f));//3维数组赋值最大，赋值0x4个3f，二维数组赋值0x7加7个f。

f[v][v][0]=f[v][v][1]=0;//f[i][j][0]表示熄灭i-j区间的灯的花费且站在i点,f[i][j][1]表示站在j点

for(int j=v;j<=n;++j)//j从v到最终

for(int i=j-1;i>=1;--i)//i从j-1到1，第一次循环用到f[j][j][1||0],之后第一维的数一直减小，用之前更新过的来更新它（这是倒序的原因）

{

f[i][j][0]=min(f[i+1][j][0]+(sum[i]+sum[n]-sum[j])*abs(x[i]-x[i+1]),f[i+1][j][1]+(sum[i]+sum[n]-sum[j])*abs(x[i]-x[j]));

f[i][j][1]=min(f[i][j-1][1]+(sum[i-1]+sum[n]-sum[j-1])*abs(x[j-1]-x[j]),f[i][j-1][0]+(sum[i-1]+sum[n]-sum[j-1])*abs(x[i]-x[j]));

}

printf("%d ",min(f[1][n][0],f[1][n][1]));

return 0;

}