关路灯(power.cpp)
【问题描述】 某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。 现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位:m）、功率（W），老张关灯所用的时间很短而可以忽略不记。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不能再消耗电了）。 【输入】 文件第一行是两个数字n（0<n<50，表示路灯的总数〉和c（1<=c<=n老张所处位置的路灯号〉； 接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。 【输出】 一个数据，即最少的功率（单位：J，1J=1W•s）。 【样例】 power.in 5 3 2 10 3 20 5 20 6 30 8 10 power.out 270 {此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序} 其实这道题关掉的路灯总是连续的，再从中向在两边找 #include<cstdio> #include<iostream> #include<cstring> #include<cmath> const long long INF = 0xefffffff; using namespace std; long long light[1005][1005][2]; long long w[1005][3],po[1005]; int n,c; int dp(int l, int r,int p) { int P = (p == 0) ? l : r; if(light[l][r][p]) return light[l][r][p]; if(l == 1 && r == n) return light[l][r][p] = 0; long long& ans = light[l][r][p] = INF; if(l-1 >= 1) { long long tmp = abs(w[P][2] - w[l-1][2]); ans = min(ans,dp(l-1, r, 0) + tmp * (po[n] + po[l-1] - po[r])); } if(r+1 <= n) { long long tmp = abs(w[P][2] - w[r+1][2]); ans = min(ans,dp(l, r+1, 1) + tmp * (po[n] + po[l-1] - po[r])); } return ans; } int main() { freopen("power.in","r",stdin); freopen("power.out","w",stdout); scanf("%d%d", &n ,&c); for(int i = 1; i <= n; i++ ) { scanf("%I64d %I64d", &w[i][2], &w[i][1]); po[i] = po[i-1] + w[i][1]; } cout << dp(c, c, 1); return 0; }