NC15447. wyh的问题
描述
我国现在能源消耗非常严重，现在政府有这样一个工作，每天早上都需要把一些路灯关掉，但是他们想让在关闭的过程中所消耗的能源是最少的，负责路灯关闭的工作人员以1m/s的速度进行行走，假设关闭路灯的时候不需要花费任何的时间，请你编写一个程序，计算在给定路灯位置和每个路灯的消耗能源的多少，求出当所有路灯关闭的时候所需要的最少能量
输入描述
多组测试数据循环输入
每组测试数据第一行：N表示路灯的数量 （2<=N <=1000）
第二行：V表示开始关灯的路灯号码。 （1<=V<=N）
接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数
D表示该路灯到原点的距离 (用米为单位来表示)，
W表示灯泡的功率，即每秒该灯泡所消耗的能量数。（0<=D<=1000，0<=W<=1000）
路灯按照顺序给出，起始位置的那盏灯不算消耗的电能里面
输出描述
输出一个整数，即消耗能量之和的最小值。
示例1
输入:
4 3 2 2 5 8 6 1 8 7
输出:
56
说明:
对于样例，我一开始在第三个路灯的位置，即在6位置C++(clang++ 11.0.1) 解法, 执行用时: 166ms, 内存消耗: 8332K, 提交时间: 2023-04-29 09:29:34
#include<bits/stdc++.h>
using namespace std;
long long d[1005],w[1005],dp[1005][1005];
int main(){
int n;
while(cin>>n){
int v; cin>>v;
for(int i=1;i<=n;i++){
cin>>d[i]>>w[i];
w[i]+=w[i-1];
}
memset(dp,0x3f,sizeof dp);
dp[v][v]=0;
for(int i=v;i>=1;i--){
for(int j=v;j<=n;j++){
dp[i][j]=min(dp[i][j],min(dp[j-1][i]+(d[j]-d[i])*(w[n]-w[j-1]+w[i-1]),dp[i][j-1]+(d[j]-d[j-1])*(w[n]-w[j-1]+w[i-1])));
dp[j][i]=min(dp[j][i],min(dp[i+1][j]+(d[j]-d[i])*(w[n]-w[j]+w[i]),dp[j][i+1]+(d[i+1]-d[i])*(w[n]-w[j]+w[i])));
}
}
cout<<min(dp[1][n],dp[n][1])<<endl;
}
}