1001: 节 能
时间限制: 1 Sec 内存限制: 128 MB
提交: 21 解决: 9
[提交][状态][讨论版]
题目描述
Dr.Kong设计的机器人卡多越来越聪明。最近市政公司交给卡多一项任务，每天早晨5：00开始，它负责关掉ZK大道右侧上所有的路灯。
卡多每到早晨5：00准会在ZK大道上某盏路灯的旁边，然后他开始关灯。每盏灯都有一定的功率，机器人卡多有着自觉的节能意识，它希望在关灯期间，ZK大道右侧上所有路灯的耗电量总数是最少的。
机器人卡多以1m/s的速度行走。假设关灯动作不需要花费额外的时间，因为当它通过某盏路灯时就顺手将灯关掉。
请你编写程序，计算在给定路灯设置，灯泡功率以及机器人卡多的起始位置的情况下，卡多关灯期间，ZK大道上所有灯耗费的最小能量。
输入
第一行： N 表示ZK大道右侧路灯的数量 （2≤ N ≤ 1000）
第二行： V 表示机器人卡多开始关灯的路灯号码。 （1≤V≤N）
接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数
D表示该路灯与ZK大道起点的距离 (用米为单位来表示)，
W表示灯泡的功率，即每秒该灯泡所消耗的能量数。路灯是按顺序给定的。
（ 0≤D≤1000， 0≤W≤1000 ）
输出
输出一个整数，即消耗能量之和的最小值。注意结果小于200，000，000
样例输入
4 32 25 86 18 7
样例输出
56
思路：做的时候没有思路，知道是DP，但是推不出来。
这道题目用区间DP的做法。设置dp[i][j][0]为关掉从i到j的所有灯，并最终处于i所在的位置时消耗的最少能量；dp[i][j][1]就表示为关掉从i到j的所有灯，并最后处于j的位置时消耗的最少能量。对于一个状态转移，从相邻的位置中得到信息，同时要考虑转移时其他电灯增加的功率损耗。诸事中写的很详细了。
代码：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1005;
struct node {
int pos,val;//pos亮灯的位置，val此位置电灯单位时间内消耗的功率
node() {pos=val=0;}
}ans[maxn];
int dp[maxn][maxn][2];
int fw[maxn][maxn];
int main() {
int n,index,totalw=0;
scanf("%d",&n);scanf("%d",&index);
for(int i=1;i<=n;i++) {
scanf("%d%d",&ans[i].pos,&ans[i].val);totalw+=ans[i].val;//totalw表示初始状态电灯功率总耗损
}
memset(fw,0,sizeof(fw));
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) {
for(int j=i;j<=n;j++) {
fw[i][j]=fw[i][j-1]+ans[j].val;//该数组表示从i位置到j位置初始状态下的功率总耗
}
}
//初始化进行分段考虑，从给定位置v向两边扩散
//v的左边
for(int i=index-1;i>=1;--i) {
//先考虑停留到左边，然后考虑回到右边
dp[i][index][0]=dp[i+1][index][0]+(totalw-fw[i+1][index])*(ans[i+1].pos-ans[i].pos);
dp[i][index][1]=dp[i][index][0]+(totalw-fw[i][index])*(ans[index].pos-ans[i].pos);
}
//v的左边
for(int j=index+1;j<=n;++j) {
//先考虑停留到右边，然后考虑回到左边
dp[index][j][1]=dp[index][j-1][1]+(totalw-fw[index][j-1])*(ans[j].pos-ans[j-1].pos);
dp[index][j][0]=dp[index][j][1]+(totalw-fw[index][j])*(ans[j].pos-ans[index].pos);
}
for(int i=index-1;i>=1;--i) {
for(int j=index+1;j<=n;++j) {
//对于dp[i][j][0]只能考虑dp[i+1][j][0|1]的状态，dp[i][j-1][0|1]没有意义。
dp[i][j][0]=min((dp[i+1][j][0]+(totalw-fw[i+1][j])*(ans[i+1].pos-ans[i].pos)),
(dp[i+1][j][1]+(totalw-fw[i+1][j])*(ans[j].pos-ans[i].pos)));
//道理同上
dp[i][j][1]=min((dp[i][j-1][1]+(totalw-fw[i][j-1])*(ans[j].pos-ans[j-1].pos)),
(dp[i][j-1][0]+(totalw-fw[i][j-1])*(ans[j].pos-ans[i].pos)));
}
}
//要么在左边，要么在右边，挑最小的即可
int result=min(dp[1][n][0],dp[1][n][1]);
printf("%d\n",result);
return 0;
}